[백준] 1874번 : 스택 수열

문제

1 ~ n까지의 수가 순서대로 들어올 때

정해진 수열을 스택을 사용해서 만들 수 있다면 연산 방법을 출력하고

불가능하다면 "NO"를 출력하라

 

접근 방식

입력을 담을 스택과 수열을 저장할 리스트 혹은 배열을 선언한다.

 

43687521 라는 수열이 주어진 경우

4가 먼저 나와야하니 4를 넣자마자 빼줘야한다.

 

push(1);
push(2);
push(3);
push(4);

pop(); // 4
pop(); // 3

 

위와 같이 4까지 모두 넣어준 후에

4와 3을 빼주고 리스트에 넣어주면 43 수열이 완성된다.

 

다음으로 나와야 하는 수는 6이기 때문에 마저 스택에 수를 넣어주고

주어진 수열을 완성할 수 있는지 판단하면 된다.

 

즉, 스택에 값을 계속 넣어주면서 넣어준 값이

수열과 일치하는 경우 빼주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());
		int index = 0;

		Stack<Integer> stack = new Stack<>();

		int[] sequence = new int[n];
		int[] result = new int[n];

		for (int i = 0; i < n; i++) {
			sequence[i] = Integer.parseInt(br.readLine());
		}

		for (int i = 1; i <= n; i++) {
			stack.push(i);
			sb.append("+\n");

			while (!stack.isEmpty() && stack.peek() == sequence[index]) {
				result[index++] = stack.pop();
				sb.append("-\n");
			}
		}

		if (result[n - 1] == 0) {
			System.out.println("NO");
		} else {
			System.out.println(sb);
		}
	}
}