스택 수열 백준 1874번

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

문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

사실 예제를 봐도 무슨 말인지 한눈에 들어오지 않아서 고민을 좀했다.

예제 1번: 4 3 6 8 7 5 2 1

수열이 위 처럼 주어져있다고 가정을 하자. 그리고 나는 1부터 n까지 숫자를 차례대로 스택에 집어 넣을 것인데 pop을 할때 제시된 수열 순서대로 뽑을 수 있는가? 물어보는 문제이다.

[1,2,3,4] 예시로 보자면 일단 4까지는 집어 넣게 되고 4와 3을 pop 한다.

[1,2,6] 그리고 그 다음 수인 5,6 까지 넣고 6을 pop

[1,2,7,8] 7과 8을 넣고 세번 pop 해서 8,7,2,1

pop 한 숫자를 보면 4 3 6 8 7 5 2 1 순서대로 나온 것을 확인 할 수 있다. 다음 예제를 보자

예제 2번 1, 2, 5, 3, 4

[1] 1을 넣고 pop한다.

[2] 2를 넣고 pop한다.

[3,4,5] 5까지 넣고 5를 pop한다.

이제 3과 4를 출력해야하는데 4부터 pop을 해야하기 때문에 만들 수 없는 수열이 되었다. 그러니 NO를 출력한다.

입력 조건 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

---

n이 주어지는데 숫자의 범위는 1부터 n까지 순서대로 주어지고 같은 정수가 두번 나오지 않는다고 했다. 그렇다면 1부터 n까지 중복된 숫자가 없다는 의미이니 넣는 최대 정수도 n으로 제한이 된다.

loop = int(input())
num_list = []
for i in range(loop):
    num_list.append(int(input()))

주어진대로 정수의 개수와 수열을 입력받는다.

stack_list=[]
print_list=[]
j=1
while True:
    if len(stack_list)!=0:
        if stack_list[-1] == num_list[0]:
            stack_list.pop()
            num_list.pop(0)
            print_list.append('-')
            continue
    if j>loop:
        break
    stack_list.append(j)
    print_list.append('+')
    j+=1
    
if len(stack_list)==0:
    print(*print_list, sep='\n')
else:
    print("NO")

아이디어는 다음과 같다.

for문은 n번만큼 반복되는 것이 아니다. 조건을 만족할때까지 반복하는 것이기 때문에 무한루프를 걸고 조건에 맞으면 빠져나오게 한다.

스택에는 1부터 차례대로 숫자가 들어가게 되는데 스택에서 빼야하는 숫자랑 지금 순열에서 나와야할 숫자가 같은지 확인을 하고 같다면 스택에서도 수열에서도 제거를 한다. pop(인덱스)이기 때문에 0을 넣으면 첫번째 숫자가 빠진다. 그리고 pusn/pop 출력은 마지막에 판단 할 것이기 때문에 리스트에다가 넣어준다.

같지 않다면 스택에다가 해당 수를 추가 해주고 j도 1 증가한다. 그리고 j가 n을 넘어가는 순간 빠져 나오는데 빠져 나오는 조건은 j가 n보다 클때가 아니라 리스트에서 더 이상 뺄 수 없을때도 포함이기 때문이기 때문에 중간에 넣었다.

최종적으로 stack_list가 비어 있다면 순열을 만들어 낼 수 있다는 의미이고 비어있지 않으면 순열을 만들 수 없다는 것이기 때문에 조건에 따라서 출력을 한다.

그런데 통과는 하는데 시간이 뭔가 많이 걸리는 걸로 봐서는 다른 효율적인 방법이 있을거 같다.