Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

18. 스택

스택을 구현하고 사용해 봅시다.

Java / Python

5. 스택 수열

1847번

스택을 활용하는 문제

이번 문제는 스택에 1 부터 n까지 수를 스택에 넣고(push) 빼는(pop) 과정을 통해 임의의 수열이 주어졌을 때 해당 수열을 만들 수 있는지를 판단하는 문제입니다. 스택에 수를 push할 때는 반드시 오름차순을 지켜야 합니다.
즉, 입력받은 value 값 까지 push 한 이력이 없을경우 stack에 value까지 push 한 후 마지막 원소를 pop해주면 되는 문제인 것 같습니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
 
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();	// 출력 결과 저장
		
		Stack<Integer> stack = new Stack<>();
		
		int N = Integer.parseInt(br.readLine());
		
		int start = 0;
		
		while(N -- > 0) {
			
			int value = Integer.parseInt(br.readLine());
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push
				for(int i = start + 1; i <= value; i++) {
					stack.push(i);
					sb.append('+').append('\n');	// + 를 저장
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위해 변수 초기화 
			}else if(stack.peek() != value) {	
				System.out.println("NO");
				return;		
			}			
			stack.pop();
			sb.append('-').append('\n');			
		}	
		System.out.println(sb);
	}
}

• Python

import sys
n = int(sys.stdin.readline())
s = []
result = []
cnt = 1
temp = True
for i in range(n):
    num = int(sys.stdin.readline())
    while cnt <= num:
        s.append(cnt)
        result.append('+')
        cnt += 1
    if s[-1] == num:
        s.pop()
        result.append('-')
    else:
        temp = False
if temp == False:
    print('NO')
else:
    for i in result:
        print(i)