[백준 1874번 문제 파이썬(python)] [스택 수열] 문제가 이상한가 이해하기 어렵다

문제

내 독해력의 문제인지 문제 자체의 문제인지 알 수 없으나 도통 이해할 수가 없었다

그래서 다른 분이 설명해둔 것(이분도 약간 잘 못 이해했다)를 보고 이해를 했다

설명

입력으로 들어오는 수열(숫자의 나열)을 스택에서 뽑아와서 똑같이 만드는게 우리의 목표이다

스택이라는 공간이 있는데 여기에는 1부터 n(첫줄에 제시되는 수)까지의 수가 오름차순으로 1부터 차례대로 들어간다

그러니 위의 예제를 예로 들면

[1...2...3...4] 까지 하나씩 스택에 넣다가

4와 수열의 첫번째 숫자가 같으니 뽑아오는 것이다

그럼 스택에는 [1,2,3]이 남게되고 우연찮게 다음 숫자가 3으로 수열의 두번 째 숫자와 같으니 또 뽑아오고

스택에는 [1,2]가 남게된다

다음 숫자는 6이므로 6과 같아질 때까지 스택을 채워주면

스택은 [1,2,5,6]이 되고 6과 같아졌으니 6을 뽑아오면

스택은 [1,2,5]가 된다

 

위의 방식으로 우리의 목표 수열을 만들때까지 반복하면 되는 것이다

아래의 예시를 보면 더 이해가 될 것이다

 

NO가 출력되어야 할 때는

수열에서 다음의 목표 숫자가 스택의 가장 최근(가장 큰) 숫자보다 작을 경우이다

위의 예시로 예를 들면

목표수열 [1,2,5,3,4]

 

스택: []

스택 채우기

스택: [1]

첫번째 목표수열 찾았으니 뽑아오기

스택: []

스택 채우기

스택: [2]

두번째 목표수열 찾았으니 뽑아오기

스택: []

스택 채우기

스택: [3,4,5]

세번째 목표수열 찾았으니 뽑아오기

스택: [3,4]

스택 채우기...

어라? 다음 목표 숫자는 3인데 채우면 안되지...

그럼 뽑아올까..

어라? 4를 뽑아오면 목표 수열이 안되는데...

 

그럼 NO를 출력해야겠다

코드

import sys

n = int(sys.stdin.readline())
nums = list(range(1, n + 1))
stk = [0]
result = []
isYes = True
for _ in range(n):
    goals = int(sys.stdin.readline())
    if goals < stk[-1]:
        print("NO")
        isYes = False
        break
    while stk[-1] != goals:
        stk.append(nums.pop(0))
        result.append("+")

    stk.pop()
    result.append("-")

if isYes:
    for i in result:
        print(i)

열심히 코드를 짜서 통과를 했지만 시간이 오래 걸려서 만족스럽지 못 했다

아래 코드는 다른 분께서 만든 내가 걸린 시간의 1/10 수준으로 통과한 코드를 가져왔다

import sys
input = sys.stdin.readline

n = int(input())

stk = []
cur = 0 # 어디까지 넣었는지 기억
res = []
flag = True  

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

    while cur < target:
        cur += 1
        stk.append(cur)
        res.append('+')

    #print(cur)

    if stk[-1] == target:
        stk.pop()
        res.append('-')
    else:
        flag = False
        break

if flag == False:
    print("NO")
else:
    for i in res:
        print(i)

나는 nums라는 리스트를 따로 만들었는데 이분은 그냥 cur이라는 변수 하나로 리스트 만드는 것을 대체했다