[백준] 17298 - 오큰수 - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

풀이과정:

처음에는 해당 인덱스 뒤로 포문을 돌려서 첫번째로 나오는 큰 수를 저장하고 break 하는식으로

풀었는데 시간과촤가 나왔다. 한 인덱스에 n번 연산이니 O(n**2)가 되므로 시간초과가 뜰만하다.

"""
#시간초과
import sys
lst_len = int(input())
lst = list(map(int, sys.stdin.readline().split()))
answer = []
for i in range(lst_len):
    found = 0
    if i == lst_len-1:
        answer.append(str(-1))
        break
    for j in range(i+1, lst_len):
        if lst[i] < lst[j]:
            answer.append(str(lst[j]))
            found = 1
            break
    if found==0:
        answer.append(str(-1))
print(" ".join(answer))
"""

 

 

 

그렇가면 빅오의 시간을 줄이려면 어떻게 해야될까, 여기서 스택이 등장한다.

스택은 현재 기준이 되는 인덱스를 나타낸다.

가령 [3, 5, 2, 7]로 예를 들면, 차례대로 인덱스 0, 1, 2, 3 이다

인덱스 0을 stack에 넣고, 1번인덱스값(5)와 비교한다.

1번 인덱스가 더 크기 때문에 정답 리스트는 -1 -> 1번인덱스 값으로 갱신된다.

이번엔 1번 인덱스와 2번인덱스값(2)를 비교했을때 2번 인덱스값이 더 작으므로,

반복문에 들어가지않고, stack에 누적된다. 그리고 나서 3번인덱스와 1번 인덱스가 다시

비교되고, 3번인덱스가 더 크기때문에 이에 따라 2번인덱스도 3번인덱스로 갱신되고,

1번 인덱스도 3번 인덱스로 갱신된다.

이렇게 스택을 활용하여 알고리즘을 짜면 O(n)로 해결이된다.

 

import sys
lst_len = int(input())
lst = list(map(int, sys.stdin.readline().split()))
answer = [-1] * lst_len
stack = []

stack.append(0)
for i in range(1, lst_len):
    while stack and lst[i] > lst[stack[-1]]:
        answer[stack.pop()] = lst[i]
    stack.append(i)
print(*answer)

답(이미지)

 

후기: 자료구조를 복습하면서, 스택 큐에 대해 어느정도 알았다고 생각했는데,

막상 활용하려니 쉽지않다..