숫자 리스트 nums가 주어졌을 때, 같은 길이의 새로운 리스트를 만들어야 합니다. 이때 인덱스 i에 들어갈 값은 nums[i]의 오른쪽에서 가장 가까운 더 큰 요소입니다. 만약 오른쪽에 더 큰 수가 없다면 리스트의 맨 앞으로 돌아가서(원형 순회) 확인하고, 그래도 더 큰 수가 존재하지 않으면 -1로 설정합니다.
예를 들어 입력이 [4, 5, 1, 3]이라면 출력은 [5, -1, 3, 4]가 됩니다.
해결 접근 방식
이 문제는 모노토닉 스택(Monotonic Stack) 기법과 두 번의 순회를 활용하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
n := 리스트 a의 크기를 저장합니다.
stack := 처음에 0을 넣어 초기화한 스택을 만들고, res := 크기가 n인 리스트를 생성하여 모든 값을 -1로 채웁니다.
0부터 1까지 총 두 번 반복합니다(원형 구조를 처리하기 위해).
i를 0부터 n-1까지 순회합니다.
스택이 비어 있지 않고 스택 꼭대기의 값 a[stack[-1]]이 a[i]보다 작은 동안 다음을 반복합니다.
res[stack[-1]] := a[i]로 설정합니다(즉, 해당 위치의 다음 큰 요소를 기록).
스택에서 마지막 요소를 제거합니다(pop).
현재 인덱스 i를 스택 끝에 삽입합니다.
최종 결과 res를 반환합니다.
두 번 순회하는 이유는 원형 리스트 특성상 뒤쪽 요소들이 앞쪽 요소들에게 '다음 큰 요소'가 될 수 있기 때문입니다. 첫 번째 순회에서 놓친 관계를 두 번째 순회에서 완성하게 됩니다.
예제 코드
class Solution: def solve(self, a): n = len(a) stack, res = [0], [-1] * n for _ in range(2): for i in range(n): while stack and a[stack[-1]] < a[i]: res[stack[-1]] = a[i] stack.pop() stack.append(i) return res ob = Solution() nums = [4, 5, 1, 3] print(ob.solve(nums))
입력
[4, 5, 1, 3]
출력
[5, -1, 3, 4]
동작 과정 설명
입력 [4, 5, 1, 3]을 예로 들면:
인덱스 0의 값 4 → 오른쪽에서 바로 만나는 더 큰 수는 5이므로 결과는 5
인덱스 1의 값 5 → 오른쪽에도, 원형으로 돌아서 확인해도 더 큰 수가 없으므로 -1
인덱스 2의 값 1 → 오른쪽의 3이 더 크므로 결과는 3
인덱스 3의 값 3 → 오른쪽에는 없지만, 원형으로 돌아가면 4가 더 크므로 결과는 4
따라서 최종 결과는 [5, -1, 3, 4]가 됩니다. 이 알고리즘은 각 요소가 최대 두 번씩만 스택에 push/pop 되므로 시간 복잡도는 O(n)으로 매우 효율적입니다.