[백준 17298] 오큰수

문제

 

www.acmicpc.net/problem/17298

17298번: 오큰수

 

처음 작성한 코드(시간초과 ㅋㅋ)

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
result = [-1] * n
stack = []
for i in range(n-1):
    for j in range(i+1,n):
        if arr[i] < arr[j]:
            result[i] = arr[j]
            break
            
print(*result)

 

코드 리뷰 후

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
result = [-1] * n
stack = []
for i in range(n):
    while(stack and arr[stack[-1]] < arr[i]):
        result[stack.pop()] = arr[i]
    stack.append(i)
    
print(*result)

1. stack에는 오큰수를 찾지 못한 원소의 인덱스를 넣을 것이다.
2. while문을 통해 오큰수를 찾으면 stack에서 하나씩 빼서 오큰수를 result에 저장한다. 

 

깨달은 점

• 다시 이 문제를 봐도 시간초과 나게 문제를 풀 것 같다 ㅎㅋㅎㅋ 어떻게 스택을 이용해서 풀지..