문제
접근
처음에 그냥 이중 포문으로 리스트 전체를 보는 식으로 구현했다.
당연하게도 시간초과가 나고… 어떻게 시간을 줄일 수 있을지 고민한 문제..
처음엔 아리송했는데, 리스트를 순서대로 보면서 자신보다 큰수가 나오면 그 수는 오큰수를 찾고 더이상 볼 필요가 없다.
반대로 큰 수가 아직 나오지 않았으면 큰 수가 나올 때까지 잘 기억해두고 있어야한다.
이걸 처리할 방법을 찾아야하는데..
[10, 7, 3, 8, 15] 가 있다.
10, 7, 3까지는 오큰수를 찾지 못했다.
8에 왔을 때 3, 7의 오큰수는 8이란걸 알 수 있다.
그리고 15에 왔을 때 10의 오큰수가 15가 된다.
리스트를 순서대로 돌면서 따로 저장해두고 있다가 맨 끝부터 하나씩 꺼내서 다음 수와 비교하는 식으로 하면 될거 같다.
스택을 쓰면 되겠구나 생각이 들었다.
스택에서 하나씩 꺼내서 다음 수와 비교한다.
스택의 꼭대기의 수가 다음 수보다 작으면 오큰수를 찾았으니 스택에서 꺼낸다.
다음 수보다 스택 꼭대기에 있는 수가 더 크면 그냥 넘어가도 된다. 스택의 아래쪽은 볼 필요가 없다.
스택의 꼭대기보다 항상 더 클테니까
스택에 숫자(배열의 값)를 넣으면 비교는 쉽겠지만 해당 숫자가 배열에 어디있는지 찾기가 너무 힘들어진다.
스택에 배열의 인덱스를 넣어서 비교하는 식으로 구현했다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split(' ')))
result = [-1] * n
stack = []
stack.append(0)
for i in range(1, n):
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop(-1)] = arr[i]
stack.append(i)
for item in result:
print(item, end=' ')