17298번 오큰수

문제

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

얼마전에 본 코테에서 본 문제랑 유사하다. 한시간 정도 시간 끌다가 테케 거의 다 실패해서.. 눈물 머금고 문제 리뷰 남기기 ( ˃̣̣̥᷄⌓˂̣̣̥᷅ )

접근 방식

수열의 크기가 1000000므로, 이중으로 loop를 쓸 순 없다.

스택으로 접근 시 loop 한번만 돌고 해결할 수 있는데, 모든 숫자들을 차례대로 순회하면서 현재 숫자 arr[idx]와 stack의 top arr[top]을 비교하여 현재 숫자가 더 크면 정답 배열 res[stack.pop()]을 채워가면 된다.

코드

n = int(input())
arr = list(map(int, input().split()))

res = [-1] * n

stack = [0]
for idx in range(1, n):
    while stack and arr[stack[-1]] < arr[idx]:
        res[stack.pop()] = arr[idx]
    stack.append(idx)

print(*res)

막상 풀어보니 정말 간단한 알고리즘이라 아쉬움이 크다..

기업 코테들을 접해보니 오히려 애매하게 알 때 더 비효율적으로 시간 잡아먹게 되는 거 같다 제대로 공부하자 🙌