1874

날짜 : 2022. 10. 30

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline()) # 수열의 크기
stack = []
cur = 1 # 현재 최대 숫자
res = []
check = True

for i in range(n):
    t = int(sys.stdin.readline()) # 수 입력
    while cur <= t: # 입력받은 값까지 오름차순으로 push
        stack.append(cur)
        #print(stack)
        cur += 1
        res.append('+')
    if t == stack[-1]: # 스택 마지막 값과 같은 경우
        stack.pop()
        #print(stack)
        res.append('-')
    elif t < stack[-1]: # 입력한 값이 이미 스택에 있는 경우(pop 했을 때 구현 x)
        check = False
if check:
    for i in res:
        print(i)
else:
    print("NO")

 

시간초과

import sys

n = int(sys.stdin.readline())
base = [] # 입력받은 수열
for i in range(n):
    base.append(int(sys.stdin.readline()))
sorted_num = sorted(base) # 오름차순 정렬된 수
temp = []
res = []
res_n = []

i = 0
check = True
while sorted_num:
    if base[i] >= sorted_num[0]:
        temp.append(sorted_num.pop(0))
        res.append('+')
        """print("일반 수열 : ", sorted_num)
        print("stack : ", temp)"""
    if base[i] == temp[-1]:
        res_n.append(temp.pop())
        res.append('-')
        i += 1
        """print("일반 수열 : ", sorted_num)
        print("stack : ", temp)"""
if len(sorted_num) == 0:
    while temp:
        res_n.append(temp.pop())
        res.append('-')
        i += 1
        """print("일반 수열 : ", sorted_num)
        print("stack : ", temp)"""

if res_n != base:
    print("NO")
else:
    for i in res:
        print(i)

 

알게된 점

- stack 타입을 이용해 수열의 조건을 구현하는 문제였다.

- 숫자는 오름차순으로 진행하되 pop과 push만을 이용해 수열을 구현하는 문제였다.

- current를 활용해서 문제를 풀이하는 방향을 얼추?? 맞았던 것 같은데 시간초과가 발생했다.

- 전부 입력받은 다음 이를 정렬하고 이중 반복문을 사용하는 바람에 시간복잡도가 지나치게 크게 나타난 듯 하다.

- 그래서 다른 풀이를 찾아봤고 입력과 동시에 스택에 push하는 방식의 코드가 있었다.

- 머릿속에 풀이방향은 잡히는데 이를 끄집어내서 코드로 구현하는게 되게 어렵다ㅠㅠ

 

 

참고 사이트

- https://hongcoding.tistory.com/39

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