[BOJ] 1874번 스택 수열

문제

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

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

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

<예제>
8				+			 	  	    5			NO
4				+						1
3				+						2
6				+						5
8				-						3
7				-						4
5				+
2				+
1				-
				+
                +
                -
                -
                -
                -
                -
                  

나의 해결

N = int(input())
answer = []  # 구해야 할 배열
stack_in = []  # 넣었다 뺄 stack
stack_out = []   # 만들 stack

# [4, 3, 6, 8, 7, 5, 2, 1]
# 1. 순서대로의 수 만큼 stack_in에 push한 후 pop으로 빼서 stack_out에 push
# 2. pop으로 해당 수를 빼낼 수 없으면 no 반환

for i in range(1, N + 1):
    n = int(input())
    answer.append(n)

cur_num = 0

for i in range(1, N + 1):                    # stack_in의 마지막이 pop할 수와 같을 때
    if len(stack_in) != 0 and stack_in[-1] == answer[i - 1]:
        in_pop = stack_in.pop()
        print("-")
        stack_out.append(in_pop)

        if in_pop > cur_num:
            cur_num = in_pop

    else:                                    # 해당 수까지 in에 넣고 해당 수를 pop한 후 out에 push
        for j in range(cur_num + 1, answer[i - 1] + 1):
            stack_in.append(j)
            print("+")
        in_pop = stack_in.pop()
        print("-")
        stack_out.append(in_pop)

        if in_pop > cur_num:
            cur_num = in_pop

문제점

• 두번째 예제에서 [1, 2, 5, 4, 3]으로 수열이 생겨버림
• 수열이 만들어지지 않는 경우에 대한 조건 부족

해결하려는 노력

• result라는 리스트를 만들어 정답 부호를 하나씩 넣어서 출력
• cur_num = N 이 된 순간부터는 stack_in[-1] 값이 pop해야하는 수와 다르면 result.clear() 후 NO 출력
• 예제의 답은 잘 구했졌지만 출력초과 등 난잡한 코드를 정리해야할 필요성을 느낌

    if cur_num == N:
        if stack_in[-1] != answer[i - 1]:
            result.clear()
            print("NO")
            break
            

다른 해결 방법

1. cnt < n 일 때까지 while문을 돌려 stack에 push (cnt += 1)
2. stack[-1] == n 이면 pop, result에 부호 넣어줌
3. 아니라면 result에 NO 반환


- 생각방식은 같은데 구현을 훨씬 간결하게 해줌!
- for 대신 while 사용했어야함
- answer, stack_out과 같은 리스트는 불필요

N = int(input())
cnt = 0
stack = []  # 넣었다 뺄 stack
result = []

for i in range(0, N):
    n = int(input())

    while cnt < n:
        cnt += 1
        stack.append(cnt)
        result.append("+")

    if stack[-1] == n:
        stack.pop()
        result.append("-")

    else:
        result.clear()
        print("NO")
        break

for i in result:   		# ->   print("\n".join(result))
    print(i)

1874번 문제해결