(C++) [백준 17298번] 오큰수

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

문제

크기가 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)을 공백으로 구분해 출력한다.

 

2493번 탑 문제나 (https://www.acmicpc.net/problem/2493) 6198번 옥상 정원 꾸미기 문제 (https://www.acmicpc.net/problem/6198) 와 상당히 비슷한 문제같다. 실제로 푸는 방법도 거의 비슷했고

 

탑 문제를 풀었는데도 비슷한 문제라 느껴지는 옥상 정원 꾸미기가 전혀 이해가 안 되어서, 코드를 보고도 한참을 고민했다. 사실 아직도 완벽하게 이해한건 아닌데 (왜 꼭 스택을 써야만 하는지, 이 코드도 얼핏 보기에는 최악의 경우 O(N^2) 같은데 통과되는지 등등) 어쨌든 내가 비슷한 문제를 풀 때 짤 수 있게 되었으니까 대충 만족하려고 한다.

 

옥상 정원 꾸미기와 거의 유사한 패턴으로 풀었다.

1. 이 문제에서 오큰수가 뜻하는 것은 수열에서 어떤 수 A[i]가 있다면, 그 A[i]보다는 뒤에 있는 인덱스를 가진 수면서 값도 더 커야한다는 뜻이다. 결국 어떤 수 A[i]가 스택에 존재한다면 스택에 있는 원소보다 큰 원소를 찾으면 된다는 뜻이다.

2. 따라서 스택의 top에 있는 원소가 내가 반복문으로 볼 A[i]의 다음 원소보다 작거나 같다면(== A[i]가 top의 원소보다 크다면) 이 원소를 스택에서 pop해주면 된다.

3. 그리고 A[i]을 스택에 다시 push하면 이 A[i]의 오큰수도 찾을 수가 있게 된다.

 

되게 고민하던게 스택에 있는 top이 아닌 원소가 현재 보고있는 수보다는 작은데 top보다는 큰? 예를 들면

7

---   A[i]의 현재 원소 : 4 -> 이런 경우를 생각했는데 애초에 이런 경우는 3<=7에서 먼저 걸러지니까 상관이 없더라

3

 

근데 스택을 꼭 써야만 하는 문제인가? 싶기는 하다... 나는 이 문제 풀때 pair 이용해서 인덱스도 저장했는데 그럼 굳이 스택 아니어도 그냥 vector로도 풀수 있지 않나??싶은데 고민을 해결해줄 사람이 없어서 아쉽긴 하다

어쨌든 나답지않게 한번에 맞춰서 좋았다.