스택 수열

풀이

 스택 자료구조 관련한 문제로 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지 묻는 문제다. 특이점으로는 스택에 push 하는 순서는 반드시 오름차순이어야 한다.

따라서 1부터 1씩 증가시키면서 현재 수열 값과 비교해보면 된다. 이 문제의 핵심 아이디어는 아래와 같다.

• if 현재 수열 값 >= 오름차순 자연수, 스택에 push, '+' 저장

• if 현재 수열 값 < 오름차순 자연수, 스택에서 pop

  • if pop() == 현재 수열 값, '-' 저장
  • else, NO 출력

시간복잡도 : O(N)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        List<Character> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int number = 1;
        boolean flag = true;
        while (N-->0){
            int x = Integer.parseInt(br.readLine());
            while (number<=x){
                stack.push(number++);
                list.add('+');
            }
            if(number>x){
                int tem = stack.pop();
                if(tem==x){
                    list.add('-');
                }
                else {
                    bw.write(String.valueOf("NO")+"\n");
                    flag = false;
                    break;
                }
            }
        }
        if(flag==true) {
            for (int i = 0; i < list.size(); i++) {
                bw.write(String.valueOf(list.get(i)) + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

Python

import sys
n = int(input())

data = []
stack = []
result = []
for _ in range(n):
    data.append(int(sys.stdin.readline()))
cnt = 1
for x in data:
    while(cnt <= n+1):
        if cnt <= x:
            stack.append(cnt)
            result.append('+')
            cnt += 1
        else:
            t = stack.pop()
            if t == x:
                result.append('-')
                break
            else:
                print("NO")
                exit(0)

for i in result:
    print(i)