[백준] 1874번 스택수열(python)

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

1874번: 스택 수열

 

1. 난이도 실버2 (🥈)

 

도대체 이게 무슨 문제인가 한참을 고민하다가 풀었다.

 

결론적으로 말하자면 stack을 적절하게 이용해서 input 의 순서와 같은 수열을 만들어 내는 것이다!

 

예제 입력 1을 보면 4-3-6-8-7-5-2-1 순서로 입력되는데, stack에서 pop한 값이 이 순서대로 나오면 된다.

 

 

2. 내가 작성한 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip())

result_num = [] #스택 수열
input_num = [] #1이상 n이하 정수
stack = []
answer = [] #부호 입력

for i in range(1,n+1):
  result_num.append(int(input().rstrip()))
  input_num.append(i)

for i in range(len(result_num)):

  while len(stack) == 0 or stack[-1] != result_num[i]:
    if len(input_num) == 0 and stack[-1] != result_num[i]:
      print("NO")
      exit()
    
    stack.append(input_num[0])
    input_num.pop(0)
    answer.append("+")

  stack.pop()
  answer.append("-")
  
for i in range(len(answer)):
    print(answer[i])

 

시간복잡도도 증가하고, 굳이 필요없는 조건들까지 확인해야 하는 식이다

 

답은 맞았지만 비효율적인 코드를 고치기 위해 열심히 구글링을 했다

 

3. 수정 코드

import sys
input = sys.stdin.readline

check = True #stack을 만들 수 있는 지 없는 지 확인
cnt = 1
stack = []
answer = [] #연산자 넣을 list

n = int(input().rstrip())

for i in range(n):

  num = int(input().rstrip())

  while cnt <= num:
    stack.append(cnt)
    answer.append("+")
    cnt+=1

  if stack[-1] == num:
    stack.pop()
    answer.append("-")
  
  else:
    check = False
    break

if check == False:
  print("NO")

else:
  for i in answer:
    print(i)

 

어차피 stack에는 오름차순 정렬만 할 수 있기 때문에

 

num(현재의 스택 수열 값)과 stack에 들어있는 최대값이 같아졌을 경우

 

stack[-1]과 num이 같은지 확인해주면 된다.

 

이렇게 한다면 모든 수를 확인해볼 필요 없이 스택 수열을 만들 수 없는 것을 찾을 수 있다.

 

 

 

 

 

내가 처음 제출한 코드와 다음에 제출한 코드를 살펴보면 시간이 10배 차이가 난다.

 

이 문제에서는 데이터의 크기가 작았어서 통과되었지만,, 데이터의 크기가 컸다면 시간초과가 발생했을 것이다. 

 

여윽시 효율적인 코드를 짜기 위해서는 많은 고민이 필요한 것 같다.