문제링크: https://www.acmicpc.net/problem/17298
이름이 근본이 없지만.. 스택과 정렬이 섞인 문제중 조금 생각해볼 거리가 있는 좋은 문제인거 같아서 풀어보았습니다.
Problem
한 숫자열이 주어집니다. 그리고 각 인덱스마다 해당하는 오큰수를 찾으면 되는데, 오큰수란 해당 인덱스의 수보다 오른쪽에 있는 수들 중, 가장 왼쪽에 있는 수를 지칭합니다. 그런수가 없다면, 오큰수는 -1이 됩니다. 문제의 예시로 나온 a=[3,5,2,7] 이라는 숫자열에서 오큰수들은 [5,7,7,-1] 이 되겠습니다.
Approach & Solution
처음 문제를 보고 좀 많이 헤멧습니다. 문제 설명처럼 오른쪽에서 가장 큰 수를 찾는것이니, 당연히 왼쪽부터, 작은 인덱스부터 서칭을 해 나간다고 생각했습니다. 거기에 스택까지 활용하라는 말에, 뭐지.. 했습니다. 당연히 O(n^2)짜리 이중 반복문을 생각해봤지만, 제한시간 1초라는 것에서 바로 틀린 접근이라는것을 알았습니다. 결국 조금 힌트를 봤는데, '이 숫자는 어느 인덱스의 오큰수가 될까' 가 시발점이었습니다.
저 말을 이해하면 풀이는 굉장히 쉬워집니다. 먼저 자신보다 큰 수가 나올때까지 스택에 인덱스를 푸쉬합니다. 더 큰수를 마주치면, 그 수가 스택안에 있는 인덱스의 오큰수가 되는겁니다.
n = int(input())
target = list(map(int,input().split()))
stack = [0]
result = [-1] * n
for i in range(len(target)):
while stack and target[stack[-1]] < target[i]:
result[stack.pop()] = target[i]
stack.append(i)
print(' '.join(map(str,result)))
Conclusion
어쩔수 없이 힌트를 본 문제였는데, 힌트에서는 패턴을 먼저 찾더라구요. 예시에서 '어떻게 7,7 이 이렇게 연속으로 나올 수 있지?' 라는 생각으로 패턴을 먼저 잡고, 패턴에 적합한 자료구조를 가지고 접근을 하는게 킬러였습니다. 단순히 내용뿐만 아니라, 문제 자체의 접근법을 배운것 같아 의미있는 문제였습니다.
