[백준 17298번] 오큰수

17298번: 오큰수

n = int(input())

elements = list(map(int,input().split()))

stack = []
answer = []

for i in range(n-1,-1,-1):
    while True:
        if len(stack) == 0:
            answer.append(-1)
            stack.append(elements[i])
            break

        if elements[i] < stack[-1]:
            answer.append(stack[-1])
            stack.append(elements[i])
            break
        else:
            stack.pop()

answer.reverse()

for i in answer:
    print(i,end=" ")

이번 문제는 해당 인덱스에 오른쪽에 위치하는 가장 가까운 수 중 현재 위치의 수보다 큰 수를 구하는 문제이다.

 

이 문제를 2중 for문으로 풀게 되면 O(N^2) 시간복잡도를 가지게 되어 시간초과가 발생하게 된다.(1,000,000 * 1,000,000)

 

따라서 스택 자료구조를 사용해서 스택이 비어있는 경우에는 -1을, 현재 값보다 스택의 마지막 값이 더 큰 경우에는 스택의 마지막 값을, 그리고 현재 값보다 작은 경우에는 현재 값보다 더 큰 숫자를 찾을 때까지 pop 하여 값을 찾는 방식으로 풀이하였다.

 

시간복잡도를 고려하여 풀이할 때는 스택이나 큐 자료구조를 사용해야 한다는 것을 다시 한번 복습할 수 있던 문제였다 :)