[백준 파이썬] # 1874 스택 수열

Silver III

# 1874 스택 수열

링크 : https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

풀이

N = int(input())
stack = []  # 숫자를 담을 리스트
result = []  # '+' or '-'을 담을 리스트 
cnt = 1  # 입력값의 경우의 수를 제한하기 위해 사용하는 기준
temp = True  # 오류 판별에 사용 

for i in range(N):
    num = int(input())

    # case 1
    while cnt <= num:
        stack.append(cnt)
        result.append('+')
        cnt += 1

    # case 2
    if stack[-1] == num:
        stack.pop()
        result.append('-')

    # case 3
    else:
        temp = False

if temp == False:
    print('NO')
else:
    for i in result:
        print(i)

 

후기

• 혼자 풀 때, 시간초과에서 개선 방법을 찾지 못해 풀이를 중단했다.
• 풀이방식에 자유롭게 생각하는 폭을 정해야 할 듯 하다. 혼자 풀 때 deque와 popleft를 활용하는 방법을 시도했었다 (어이 문제 제목부터가 스택 아니냐구..)

깨지고 부서져라님의 풀이가 도움이 되었다

• 오류 판별을 위해 try-except를 사용하기보다 temp=True를 사용하는 간단한 방식이 도움이 된다 #1
• 기준이 되는 변수(cnt)를 설정하는 방식이 연산시간을 줄이는데 도움이 된다 #2
• for문이 돌면서 새롭게 입력되는 값(num)은 3가지 경우 수를 갖는다 #3
  • stack[-1] = num : pop 해주고, result에 '-'를 append 한다
  • stack[-1] > num : 오류에 해당
  • stack[-1] < num : stack에 cnt를 추가해주면서 result에 '+'를 append