[PS] BOJ1874 스택 수열 ( 자료구조 ) with Python, JAVA

@문제

1874번: 스택 수열

 

 

@문제풀이

 

STACK의 구조를 이해하는 문제이다.  두 가지 포인터가 필요하다. 

 

current : STACK에 PUSH 되었던 가장 큰 수

top : STACK에서 가장 먼저 POP되는 값 

 

STACK에 오름차순으로 PUSH 되므로 입력값이 current보다 커야 PUSH를 할 수 있다. POP은 입력값과 top이 같아야 한다. 만약 top과 입력값이 다르면 STACK으로 구현할 수 없는 수열이다. 

 

정리하면,

IF 입력값 > current : PUSH로 STACK을 채운 후, POP 진행

ELSE : POP 진행

( 단, 입력값과 top가 다르면 종료 )

 

@코드 

 

Python

import sys
input = sys.stdin.readline

n = int(input())
stack = []
result = []
flag = True
current = 0

for _ in range(n) :
  value = int(input())
  while current < value : #PUSH
    current += 1
    result.append("+")
    stack.append(current)
    
  if stack[-1] == value : #POP
    stack.pop()
    result.append("-")
  else : 
    flag = False
    break

if flag :
  for op in result :
    print(op)
else :
  print("NO")

 

JAVA

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        boolean flag = true;

        int pointer = 1;
        for(int i=1;i<=n;i++){
            int k = Integer.parseInt(br.readLine());
            while(pointer <= k ){
                stack.push(pointer++);
                sb.append("+").append("\n");
            }
            if(stack.peek() == k){
                stack.pop();
                sb.append("-").append("\n");
            }else{
                System.out.println("NO");
                return;
            }
        }

        System.out.println(sb);
    }
}