✅ stack

문제

링크

풀이

1. 문제 접근

처음에 든 생각은 i보다 오른쪽에 있는 원소중에 Ai보다 큰 원소들을 vector에 저장하여 정렬 후 가장 큰 값을 뽑아 내는 방법을 떠올렸지만
원소의 범위가 최대 1,000,000 이다.. 이방법으로는 분명 시간초과가 날 것이다.

위처럼 i 오른쪽의 원소들을 매번 다 돌면서 Ai보다 큰 최초의 수를 찾을 수 없기 때문에
i 의 오큰수를 찾지말고 i의 이전 수들 중에 Ai가 오큰수가 되는 수들을 찾아 처리해주면 중복 탐색을 줄일 수 있다.
심지어 오큰수는 가장 왼쪽에 있다고 했으므로 얼마 안가 Ai가 오큰수인 수들을 찾을 수 있을 것 같다.

2. 자료구조 선택과 그 이유

위의 방법을 사용하기 위해 i 이전 수들 중에 오큰수를 아직 찾지 못한 수들을 저장해두고 i 마다 Ai가 오큰수인지 판별해야 한다.

i-1과 i-2가 아직 오큰수를 찾지 못했다면 Ai-2 > Ai-1 일것이다. 여기서 Ai가 i-1의 오큰수가 아니라면 당연히 i-2의 오큰수도 아니다.
따라서 아직 오큰수를 찾지 못한 인덱스들을 최근에 나온 인덱스부터 비교해야한다.
즉, 인덱스를 반대로 저장할 수 있는 stack을 사용하면 편할 것 같다.

3. 문제 해결 로직 (풀이법)

순서대로 수열을 돌면서
1. stack이 비어있지 않으면 stack.top 과 Ai를 비교하고 stack.top < Ai 라면 stack.pop을 해주고 pop해준 인덱스의 오큰수를 저장한다.
2. i번째 또한 오큰수를 아직 구하지 않았으므로 stack.push 해준다.

의사코드

cin >> N
for(i : 0~N-1){
	cin >> arr[i] // 입력된 수열
}

fill(answer,-1) // 오큰수 없을 경우 -1이어야 함

for(i : 0~N-1){
	while(!stack.empty && arr[stack.top] < arr[i]){
    	answer[stack.top] = arr[i] // answer : 오큰수 저장 배열
        stack.pop
    }
    
    stack.push(i)
}

cout << answer

4. 시간 복잡도 분석

O(N)..?

5. 문제에서 중요한 부분

본문제에서 stack을 떠올리기 조차 쉽지 않았다.
수열을 돌면서 i의 오큰수를 구하는게 아니라 i의 이전 수들 중에 Ai가 오큰수가 되는 수들을 찾아 처리한다는 생각의 전환이 필요했던 문제