[Python] 1874번 : 스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

 

문제 3줄 요약

1. 1 부터 n까지의 수를 스택에 넣었다가 뽑는다.

2. 뽑은 수들로 수열을 만들 것이다.

3. 만들고자 하는 수열이 주어지는데 만들기 가능하다면, push와 pop 연산 순서대로 출력. 불가능이면 "NO" 출력

 

 

 

예제를 보고 처음엔 주어진 수열이 어딨는거지?

찾고 있었다 ㅋㅎ...

 

위의 예제 첫 번째 N은 수열의 수를 순서대로 출력한다.

즉, 8개인 수열 "4-3-6-8-7-5-2-1" 을 만들고자 한다.

 

거기에 필요한 연산은

1 ~ N 까지의 수 중

일단 4까지 push 해야 수열의 첫 번째 원소인 4를 pop 해올 것이다.

 

고로 push 4번(= "+" 를 4번 출력) 하면,

stack에는 [ 1-2-3-4 ] 에서 pop을 한번하여

stack : [1-2-3]가 남아있고, 수열: "4" 하나를 채울 수 있다.

 

위의 push와 pop 연산을 반복하여,

수열을 만들면 된다!

 

 

---

 

하지만

수열을 완성시키지 못하는 경우도 있다.

수열 "1-2-5-3-4" 를 만들고자 하는데,

"+", "-", "+", "-" 를 해주면

1과 2는 채울 수 있다.

 

하지만 5를 채우기 위해선

5까지 push를 해줘야한다.

"+", "+", "+", "-" 해주면

stack : [3-4] 가 남아 있을 것이며, 그 다음 뽑아야할 수는 3이다.

 

하지만 스택은 LIFO(후입선출) 구조.

4가 먼저 나오게 되므로, 이 수열은 만들 수 없는 수열이다.

 

---

 

머리론 이해했다.

코드로 작성해보자!

 

push와 pop 연산을 idx로 리스트를 이동해가며,

수열의 각 자리의 숫자와 비교해주었다.

위의 경우처럼,

스택의 마지막 원소가 뽑고자하는 수열보다 큰 경우는

break로 for문을 통과시켜

 

마지막에

스택에 문자가 남아있는 경우, "NO"를 출력하는 방식으로 구현하였다.

 

 

from sys import stdin

if __name__ == "__main__":
    N = int(stdin.readline())
    # num_list는 스택 구조, stack은 만들고자 하는 수열
    # answer_list는 출력, visited는 방문 체크를 한다.
    num_list, stack, answer_list, visited = [], [], [], [True] * N
    for _ in range(N):
        stack.append(int(stdin.readline()))
    
    idx = 0
    for compare in stack:
        while(idx < N):
            idx += 1
            # 1부터 차례대로 첫 수열과 같은 수가 올 때까지,
            # push 연산 해주며 방문 체크를 한다.
            if compare >= idx and visited[idx-1] and idx>0:         
                num_list.append(idx)
                answer_list.append("+")
                visited[idx-1] = False
            
            # push할 숫자(idx)가 수열의 숫자보다 큰 경우,
            # stack에 담겨있는 마지막 수로 idx를 변경
            elif compare < idx:
                idx = num_list[-1]
                # 스택의 마지막 수가 비교할 수열보다 크다면,
                # 지울 수 없는 문자. 즉 "NO"
                if compare < idx:
                    break
            
            # push할 숫자와 수열의 수가 같은 경우,
            # push한 수를 다시 pop하고, 그 전의 수를 비교해준다.
            if compare == idx:
                num_list.pop()
                answer_list.append("-")
                idx -= 2
                break
    
    # 스택에 남아있는 문자가 있다면,
    # 만들 수 없는 수열이므로 "NO" 출력.
    if len(num_list):
        print("NO")
    else:
        for pm in answer_list:
            print(pm)

 

어렵진 않았지만,

작성하다 보면 실수가 생겨 무한루프도 돌고..

신중하게 풀어야 하는 문제였다.

 

끝!