인사말

안녕하세요. 송민선입니다.

어느덧 알고리즘 스터디를 시작한 지 3주 째가 됐네요.

하다보니 점점 더 익숙해지는 것 같기도 하면서 어려운 문제가 나오면 현타가 씨게 오네요…

다들 꾸준히 열심히 해봅시다!!

문제해석

이번 문제는 꽤나 저한테 난이도가 있는 편이었습니다.

간단히 문제를 보자면

입력

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


출력

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

간단하게 예시를 들자면

입력

4

2

3

4

1

이면

step 1
push
스택 => [1]

step2
push
스택 => [1,2]

step3
pop
스택 => [1]
수열 => 2

step4
push
스택 => [1,3]
수열 => 2

step5
pop
스택 => [1]
수열 => 2 3

step6
push
스택 => [1,4]
수열 => 2 3

step7
pop
스택 => [1]
수열 => 2 3 4

step8
pop
스택 => []
수열 => 2 3 4 1

와 같이 나오기 때문에 출력값으로

+
+
-
+
-
+
-
-

가 나오게 됩니다.

풀이방법

import sys

num = int(sys.stdin.readline())
stack_list = []
answer_list = []
count = 1
is_valid = True

for i in range(num):
    value = int(sys.stdin.readline())

    while count <= value:
        stack_list.append(count)
        answer_list.append("+")
        count += 1

    if stack_list[-1] == value:
        stack_list.pop()
        answer_list.append("-")
    else:
        is_valid = False

if is_valid:
    for i in answer_list:
        print(i)
else:
    print("NO")

마무리

처음엔 무작정 [1,2,3,4,5,6] 이런식으로 스택을 만들어주고 그 스택을 기반으로 반복문을 썼더니 잘 풀리지 않았습니다.

이 문제에서 수열은 1부터 n까지 이루어진 정수가 하나씩 주어진다라는 점이 중요하였습니다.

그래서 count라는 변수를 만들어주고 처음 pop이 나오기전까지 count를 계속 더해주었습니다.

어차피 모든 수는 한번 씩 나오기 때문에 pop이 나온 후에 push과정이 필요하면 그 전 count값에서 마저 이어가도 문제가 발생하지 않습니다.

처음엔 이러한 본질을 잘 파악하지 못하여 해결하지 못했습니다.ㅠㅠ 앞으로 더 열심히 해여겠어요 ㅜㅜㅜ