190220 백준 알고리즘 문제풀기*

|

[1874] 스택 수열*

문제

  • 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
  • 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
  • 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

  • 문제 자체를 이해하는데 있어서 상당한 시간이 걸렸다.
  • 이 문제가 어떻게 돌아가는지 예시를 들어서 이해해봤다.
  • 입력
    • 8 4 3 6 8 7 5 2 1 인 경우(길이 8)
Input Stack 출력 수열
4 4 +  
  3 +  
  2 +  
  1 +  
Input Stack 출력 수열
    - 4
  ~~4~~ +  
  3 +  
  2 +  
  1 +  
Input Stack 출력 수열
3   - 4
  ~~4~~ +  
  3 +  
  2 +  
  1 +  
Input Stack 출력 수열
    - 3
    - 4
  ~~4~~ +  
  ~~3~~ +  
  2 +  
  1 +  
Input Stack 출력 수열
6 6 +  
  5 +  
    - 3
    - 4
  ~~4~~ +  
  ~~3~~ +  
  2 +  
  1 +  
Input Stack 출력 수열
    - 6
  ~~6~~ +  
  5 +  
    - 3
    - 4
  ~~4~~ +  
  ~~3~~ +  
  2 +  
  1 +  
Input Stack 출력 수열
8 8 +  
  7 +  
    - 6
  ~~6~~ +  
  5 +  
    - 3
    - 4
  ~~4~~ +  
  ~~3~~ +  
  2 +  
  1 +  

… (Stack 내부의 숫자가 위에서 아래 순서대로 지워진다.)

Input Stack 출력 수열
7   - 7
8   - 8
  ~~8~~ +  
  ~~7~~ +  
    - 6
  ~~6~~ +  
  5 +  
    - 3
    - 4
  ~~4~~ +  
  ~~3~~ +  
  2 +  
  1 +  

Input Stack 출력 수열
1   - 1
2   - 2
5   - 5
    - 7
    - 8
  ~~8~~ +  
  ~~7~~ +  
    - 6
  ~~6~~ +  
  ~~5~~ +  
    - 3
    - 4
  ~~4~~ +  
  ~~3~~ +  
  ~~2~~ +  
  ~~1~~ +  
  • 뽑아내야 할 값이 현재 스택에 없어서 저장 후 뽑아내야 하는 값이라면 push를 통해 해당 수를 만들고 바로 pop을 1번 수행해 그 수를 뽑아낸다.
  • 즉, 만일 뽑아내야 할 값이 스택에 현재 있는 값이라면 pop을 수행해야 하므로 stack에 해당 값의 유무에 상관없이 무조건 1회의 pop이 수행되어야 한다.
  • 위의 예시에서, 8 4 3 6 8 7 ~~5~~ 2 1 로 5를 제외하고 뽑아내야 하는 경우는 출력 불가능하다(Stack은 LIFO)
  • 즉, pop 연산을 통해 최상위 값만 뽑아낼 수 있는 경우를 제외하곤 모두 “NO”를 출력해야 한다.

정답

class Stack:
    def __init__(self):
        self.len = 0
        self.list = []

    def push(self, num):
        self.list.append(num)
        self.len += 1

    def pop(self):
        if self.size() == 0:
            return -1
        pop_result = self.list[self.len-1]
        del self.list[self.len-1]
        self.len -= 1
        return pop_result

    def size(self):
        return self.len

    def empty(self):
        return 1 if self.len == 0 else 0

    def top(self):
        return self.list[-1] if self.size() != 0 else -1

num = int(input()) # 몇 개의 숫자를 입력 받을지
stack = Stack() # 문제풀이를 위한 Stack 객체 선언
inputs = [] # 입력 저장용 list
outputs = [] # 출력 저장용 list
index = 0

# 입력을 받아 inputs 리스트 저장
for j in range(num):
    inputs.append(int(input()))

# 각 loop의 시작점마다 push
for j in range(1, num+1):
    stack.push(j)
    outputs.append('+')
    
    # index가 전체 숫자 개수보다 크고 스택의 맨 위 숫자가 현재번째 숫자와 
    # 같지 않다면 수열을 만들 수 없는 상태가 됨
    # 그러한 경우 while문 안에서 pop을 수행하지 못해 스택에 숫자가 남아있게 됨
    while index < num and stack.top() == inputs[index]:
        stack.pop()
        outputs.append('-')
        index += 1

# 위의 while문에 따라 스택에 숫자가 남아있게 되면 수열을 만들지 못한것이므로 NO를 출력
if not stack.empty():
    print('NO')
else:
    for j in outputs:
        print(j)