[BOJ][C++] 백준 17298번 오큰수

17298번 오큰수

1. 문제 정보

백준 온라인 저지 [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)을 공백으로 구분해 출력한다.

---

예제 입력1

4
3 5 2 7

예제 출력1

5 7 7 -1

예제 입력2

4
9 5 4 8

예제 출력2

-1 8 8 -1

---

시간 / 메모리 제한

1초 / 128MB

---

2. 생각

1. A[i]보다 오른쪽에 있으면서 A[i]보다 큰 수 중에서 가장 왼쪽에 있는 수를 출력합니다.
   i번째 수와 오른쪽에 있는 수 중 첫번째로 만나는 i번째 수보다 큰 수 사이를 모두 오른쪽에 있는 수 중 첫번째로 만나는 i번째 수보다 큰 수로 업데이트하면 됩니다.
   인덱스를 거꾸로 저장하는 스택을 사용하겠습니다.

2. 입력 값을 받을 배열 arr과 최종 결과를 담을 배열 nge, 그리고 이 알고리즘에 이용할 인덱스를 거꾸로 저장하는 스택 st를 사용합니다. nge 배열은 초기화를 -1로 했습니다.

3. i를 n까지 늘리며 인덱스 i를 스택에 집어 넣습니다.
   그 전에 체크해야할 것은 스택이 비어있는지 확인하고 비어있지 않다면 arr[st.top]의 값이 arr[i]보다 작은지도 체크합니다.
   둘다 만족한다면 오른쪽에 있는 수 중 첫번째로 만나는 i번째 수보다 큰 수를 찾은것입니다. nge의 값을 arr[i]로 모두 업데이트합니다.

4. 스택에 남아있는 경우가 있다면 그 수보다 오른쪽에서 그 수보다 더 큰 수는 없는 것입니다. -1을 출력합니다.

• 참고

  i	arr		stack		nge
  		st.top		arr[st.top]
  1	3	x -> 1		x -> 3
  2	5	1 -> x -> 2		3 -> x -> 5	nge[1]=5
  3	2	2 -> 3, 2		5 -> 2, 5
  4	7	3, 2 -> 2 -> x -> 4		2, 5 -> 5 -> x -> 7	nge[3]=7, nge[2]=7

3. 소스코드 (C++)

---

터미널의 입출력 화면 예제1

터미널의 입출력 화면 예제2