[백준] 1874번 : 스택 수열(스택)- 파이썬[Python]

문제

1874번: 스택 수열

 

풀이

import sys
n=int(sys.stdin.readline())
n_check=1 #첫번째 수열까지 탐색할 변수
stack=[] #스택 리스트
solve=[] #정답(+,-) 리스트 --> 수열을 입력받는 즉시 판단하기때문에 리스트 형식으로 담아두기
for i in range(n):
  suyeoul=(int(sys.stdin.readline())) #수열 입력
  for p in range(n_check,suyeoul+1): #n_check부터 수열입력값까지 탐색
    stack.append(p) #n_check값을 증가시키면서 push
    solve.append('+') #스택에 push
    n_check+=1
  if stack[-1]==suyeoul: #스택 마지막값이 입력값과 같다면
    stack.pop() #pop
    solve.append('-') #pop
if len(stack)!=0: #수열이 스택(push,pop)으로 정확히 만들어면 len(stack)이 0이된다 
  print('NO')
else:
  for i in solve:
    print(i)

 

알고리즘 문제를 풀다보니 일단 전부 리스트에 담고 시작하는 버릇이 생겼다.

처음 이 문제를 풀 때 1부터 n까지를 전부 리스트에 담아서 하나씩 비교하는 코드를 짰는데 시간초과가 되었다.

시간초과 처리를 받지 않으려고 반복문을 계속 지워나가면서 다시 고민해보았다.

시행착오 끝에 수열 하나하나 입력 받은 즉시 PUSH, POP을 판단하여 시간 복잡도를 n까지 줄일 수 있는 문제임을 깨달았다. 브론즈~실버 하위 문제는 일단 리스트에 담아서 풀어도 전부 정답처리되었지만, 티어가 올라갈 수록 시간초과 기준이 빡세져감을 느끼고 있다.

계속 느끼는 거지만, 효율적인 코드를 계속해서 고민해봐야하는데 그게 참 어려운 일인 것 같다. 시간과 노력이 이를 해결해 줄 것이라고 믿는다.