[백준_1874] 스택 수열

문제 보기: https://www.acmicpc.net/problem/1874

1874번: 스택 수열

문제

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

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

 

입력

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

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

새로 사용한 함수

if "NO" not in prints:

조건문에서 위와 같이 사용하게 되면 prints라는 리스트에서 NO라는 문자열이 있는지 판별 없다고 한다면 해당 내용 하위의 기능을 하게된다.

 

풀이 과정

1. 입력과 출력의 관계를 봤을때 입력에 대해서 출력이 한개씩 되는 형식이 아니고 출력물의 리스트를 마지막에 출력이 되는 형식으로 구성해야한다.

2. stack에 append를 수행할때 마지막 값은 pop을 수행해도 줄어드는 숫자가 아니기때문에 변수로 저장하여 관리할 필요가 있다. 이를 index라는 값으로 저장하고 사용하도록 하자

3. stack의 마지막 숫자를 확인하여 입력값과 같다면 바로 pop을 할 수 있다면 좋겠다. 하지만 stack에 아무것도 없을 경우에는 에러가 뜰 수 있으므로 try except문을 사용하면 편하게 핸들링이 가능할 것으로 생각된다.

4. 만약 마지막값과 입력값이 같다면 pop이 되버리고 다른 행동을 안하면 좋으므로 continue를 이용하여 for문만을 이어서 진행할 수 있게 하자

5. 마지막 출력부에서는 저장된 출력리스트에 NO가 있는지 부터 확인하고 NO가 있다면 NO만을 출력하고 프로그램을 종료시킨다

코드

N = int(input())

stack = []
index = 1

prints = []

for _ in range(N):
    n = int(input())

    try:
        if stack[-1] == n:
            stack.pop()
            prints.append("-")
            continue

    except:
        if n >= index:
            # print(index)
            for i in range(index, n + 1):
                stack.append(i)
                prints.append("+")
                if i == n:
                    stack.pop()
                    prints.append("-")

            index = i + 1
        else:
            prints.append("NO")

    else:
        if n >= index:
            # print(index)
            for i in range(index, n + 1):
                stack.append(i)
                prints.append("+")
                if i == n:
                    stack.pop()
                    prints.append("-")

            index = i + 1
        else:
            prints.append("NO")

if "NO" not in prints:
    for prin in prints:
        print(prin)
else:
    print("NO")