#1873 : 스택 수열

풀이방법

사용된 것:

Stack

 

2022.04.12

스택이 무엇인지 알면 풀 수 있는 쉬운 문제이다.

 

"NO"를 출력해야 하는 경우를 잡아내는 법을 생각해내기가 조금 어려울 수 있는데, 해결법은 다음과 같다.

이번에 수열에 추가되어야 하는 숫자가 스택에 들어있지만 top에 있지는 않은 경우, 바로 모든 것을 관두고 "NO"를 출력하면 된다.

같은 숫자를 두 번 add할 수는 없으므로, 스택의 깊은 곳에 들어가 있는 그놈을 무조건 꺼내야 수열에 추가할 수 있다.

그런데 그 숫자를 꺼내어 수열에 추가하려면 그 숫자보다 더 top에 가까운 수들을 먼저 pop해야만 한다.

pop되는 수는 무조건 수열에 추가되어버린다. 즉, 엉뚱한 수가 수열에 추가되게 된다.

그러므로 이번에 pop해야 하는 수가 스택의 top이 아닌 더 깊은 곳에 있다면 무조건 망한 것이다.

따라서

if(stack.contains(arr[cnt]) && stack.peek() != arr[cnt]) {
	System.out.print("NO");
	System.exit(0);
}

이러한 조건문을 이용하면 "NO"를 출력해야 하는 경우를 잡아낼 수 있다.

 

코드

Java(2022.04.12)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n];
		for(int i = 0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Stack<Integer> stack = new Stack<Integer>();
		
		int cnt = 0;	//수열이 얼마나 완성되었는지를 세는 인덱스
		int num = 0;	//이번에 스택에 add되는 정수를 가리키는 변수
		StringBuilder sb = new StringBuilder();
		while(cnt<n) {
			
			if(stack.contains(arr[cnt]) && stack.peek() != arr[cnt]) {
				System.out.print("NO");
				System.exit(0);
			}
			
			if(stack.isEmpty()
					||
					stack.peek()<arr[cnt]) {
				num++;
				stack.add(num);
				sb.append("+" + System.lineSeparator());				
			}
			
			
			if(stack.peek() == arr[cnt]) {
				stack.pop();
				sb.append("-" + System.lineSeparator());
				cnt++;
			}
		}
		
		System.out.print(sb);

	}

}