📚 오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

예제 입력 2

4
9 5 4 8

예제 출력 2

-1 8 8 -1

✍ 접근

for문을 두번 돌면서 오른쪽에 위치한 가장 가까운 큰 수가 나오면 하나씩 print한다 => 시간초과
따라서
1. stack을 하나 만들고
2. -1이 n개 있는 blueprint를 만든다
그 후 for문을 한번 돌리면서
1. stack에 무언가 존재하고 && arr[stack에 들어있는 마지막 값] 과 arr[i]를 비교했을 때 마지막 값보다 arr[i]가 더 크면 blueprint[stack에 들어있는 마지막 값]을 arr[i]로 바꾼다
2. stack에 i를 append한다

정답 코드

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

값 자체를 stack에 집어넣고 빼는 것이 아니라 값의 'index'를 집어넣고 빼는 점이 특징
while문에 stack이 존재할 때 && (값이라고 쳤을 때) stack의 마지막 값보다 arr[i]의 값이 클 경우에만 while문을 돈다는 점 주의
=> 두번째 예제처럼 맨 처음에 값 9(index0)이 들어가게 되면 첫 번째 값은 stack에서 pop되지 못한다
=> blueprint에 어떤 작용도 하지 못하기 때문에 -1로 남아있다 == 오른쪽에 더 큰 수가 없을 때 -1로 남아있다
while문에 들어가든, 들어가지 않든 stack.append(i)로 stack에 값을 계속 입력해준다
=> 값을 하나씩 변화시키면서 while문을 돌아야 하기 때문에

⭐ 배움

for문을 두번 도는 것은 시간복잡도에 좋지 않다
어떠한 조건 a일때 보여줘야 하는 내용'x'이 같을 때 모든 배열을 'x'로 초기화하고 조건 a가 아닐 때만 배열 요소를 교체해주는 것도 좋은 방법이다

역시 똑똑한 사람들이 너무 많다... 나는 언제쯤 더 성장할까?

열심히하자 화이팅!