[백준/자바] 1874 스택 수열

[백준/자바] 1874 스택 수열

 

📌 문제 

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다.

스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.

임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

 

⚔ 입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

 

📣 출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

 

 

 

---

 

 

 

💎 문제분석하기

 

스택의 개념을 안다면 로직 자체는 쉽다. 

 

스택의 push와 pop을 통해 입력된 값을 그대로 출력할 수 있는 상황을 묻고 있다. 

 

먼저 예제 출력 2를 생각해보면 

 

 

이와 같이 3이 입력을 해도 출력을 할 수가 없고 

출력을 한다고 해도 4,3 순으로 출력이 되어야 하니 결과적으로 요구 사항인 3을 출력하지 못한다. 

 

제시된 입력처럼 출력을 할 수 없는 상황이 되면 NO를 출력하라는 요구 사항에 따라 

NO를 출력하고 정답이 된다.

 

1번의 예제 같은 경우 입력된 숫자를 정확히 출력할 수 있다. 

 

 

마지막 125는 5, 2, 1 순서대로 빠진다. 

 

 

 

 

 

 

📜 슈도코드 작성하기 

 

 

필요한 변수를 생각해보면 

 

int N : 입력받는 수열의 개수 

배열 A : 두번째 입력받는 수열을 저장할 배열

 

Stack : 수열을 넣고 뺄 스택 

플래그 result : No의 출력을 제어할 플래그 

int accendingNumber : 오름차순의 기준을 잡을 자연수 

 

stringBuffer : 결과값 출력을 위한 stringbuffer

 

먼저 수열을 전부 저장하고 계산을 하는 방식으로 푼다. 

 

받은 수열의 수 만큼의 반복문을 돌면서 

 

해당하는 수열 (개별 입력값)이 오름차순 자연수보다 크다면 push를 하여 넣어주고 

 

만약 작다면 꺼내는데, 이때 반드시 현재 값과 같은 값이 빠져야 한다.

그렇지 않으면 NO를 출력한다. 

예시에서 3의 순서에서 4가 빠지면서 NO가 출력되는 원리. 

 

 

 

 

 

 

 

 

💡 코드 구현하기

 

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N]; // N의 개수 만큼이 들어오므로

		// 2번째 입력을 저장한다
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}

		Stack<Integer> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		int ascendingNumber = 1;
		boolean result = true;

		for (int currentNumber : A) {    // N이 개수이므로
			if (currentNumber >= ascendingNumber) {            // 현재값이 오름차순으로 설정된 값보다 크다면 넣는다
				while (currentNumber >= ascendingNumber) {
					stack.push(ascendingNumber++);
					sb.append("+\n");
				}
				stack.pop();                                // 여기서 빼는 작업은 오름차순을 맞추어주는 효과를 갖는다.
				sb.append("-\n");
			} else {        // 현재값이 오름차순으로 설정된 값보다 작다면 꺼낸다.
				int poppedNumber = stack.pop();        // 여기서 빼는 값은 반드시 현재 값과 같아져야 한다. 예시에서 3의 순서에서 4가 빠지면서 NO가 출력되는 원리.

				if (poppedNumber > currentNumber) {
					System.out.println("NO");
					result = false;
					break;
				} else {
					sb.append("-\n");
				}

			}
		}
		if (result) {
			System.out.println(sb);

		}
	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편