[BOJ]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를 출력한다.

풀이 방법:

문제를 풀기에 앞서서 문제를 이해를 하는 것조차 어려웠다. 1~n까지의 수가 있을 때 각 수를 스택 구조를 유지하는 배열에 넣었다가 빼면서 우리가 입력으로 넣은 수열을 만드는 것이 문제의 목표이다. 

 처음에는 while로 넣었다가 빼는 과정을 조절하려고 했으나 적절한 조건을 찾기 어려웠다. 그래서 예외처리 구문을 사용해서 빈 리스트에서 pop을 하려 할 때 오류가 발생해서 빠져나오도록 만들었다. 

 

 우선 입력으로 처음 넣은 값을 만들기 위해서 그 값까지 모든 값들을 계속 순차적으로 넣어야 한다. 그래서 맨 처음 i로 반복되는 for 반복문이 첫 원소를 만들기 위한 과정이다. 이후 j 반복문을 통해서 본격적으로 원하는 수열을 만들고자 한다. 일단 우선적으로 answer가 비어있다면 하나 추가를 하는 과정을 거친 뒤 stack인 answer 배열의 맨 윗 값이 원하는 값인지 비교를 하는 조건문을 만들었다. 만약 원하는 값이라면 -를 하고 그렇지 않다면 아직 answer에 들어가 있지 않은 것이라면 반복문 i처럼 계속넣어주면 되기 때문에 이번에는 while로 넣어주도록 한다. 그리고 다시 끝 값을 비교하고 빼도록 한다. 

하지만 j-for를 반복하면서 더하거나 빼는 작업을 한 번도 하지 않았다면 이 것은 문제가 생긴 경우 이므로 somethingtodo라는 부울 함수를 사용해 NO를 출력하도록 한다. (주로 빼야할 수가 이미 들어가 있을 경우 발생한다.)

n=int(input())
def sol(n):
    answer_list=[int(input()) for i in range(n)]
    answer=[]
    ans=[]
    k=0
    try:
        for i in range(1,answer_list[0]+1):
            k+=1
            answer.append(k)
            ans.append("+")
        for j in range(n):
            somethingtodo=False
            if len(answer)==0:
                k+=1
                answer.append(k)
                ans.append("+")
                somethingtodo=True
            if answer[-1]==answer_list[j]:
                answer.pop()
                ans.append('-')
                somethingtodo=True
            else:
                while answer_list[j]>answer[-1]:
                    k+=1
                    answer.append(k)
                    ans.append("+")
                    somethingtodo=True
                if answer[-1]==answer_list[j]:
                    answer.pop()
                    ans.append("-")
                    somethingtodo=True
            if somethingtodo:
                pass
            else:
                print("NO")
                return
        print(*ans,sep="\n")
    except:
        print("No")
sol(n)