[백준 알고리즘] 17298번 : 오큰수, c++

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

17298번: 오큰수

c++로 백준 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

 

 

 

 

<문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

visual studio에서는 원하는 대로 출력되었지만, 백준 사이트에서는 '시간 초과'라고 떴다. 

 

 

다시 작성한 코드는 다음과 같다.

알고리즘 복잡도를 해결하기위해 스택을 사용해야만 했다.

 

 

1. N을 선언한 후 입력받는다.

2. 0부터 N-1까지 N번 for문을 반복하며 N개의 숫자를 입력받고 계산한다.

- for 반복문 코드 내용 -

숫자 하나를 입력받는다.

while문을 통해 스택이 비었다면 index값을 스택에 저장한다.

뒤에 더 큰 숫자가 있다면 그 숫자를 arr에 저장하고 더 큰 숫자가 없다면 스택에 저장한다.

3. 스택에 수가 들어있다면 숫자들을 모두 "arr[들어있는 값]"에 -1을 저장하고 스택에 저장한 수를 뺀다.

4. 출력할 값들을 저장한 배열에 들어있는 숫자들을 하나씩 차례대로 출력한다.