[백준 17298번] 오큰수 (java)

백준 17298번 : 오큰수

17298번: 오큰수

 

res 배열에는 각 원소의 오큰수가 무엇인지를 넣어준다.

 

스택을 하나 만들고, 이 스택에는 수열 A의 원소의 인덱스(idx)가 들어간다.

- A[idx] 가 아직 오큰수를 만나지 못했다면, idx는 스택에 계속 남아있게 된다.

- A[idx] 가 오큰수를 만나면, 스택에서 idx가 pop되고, res[idx] 에는 A[idx]의 오큰수가 들어간다.

 

 

백준 문제의 첫번째 예제를 보면, 수열 A는 3 5 2 7 이다. 

우선 res의 모든 값을 -1로 초기화해준다.

 

<1>

제일 먼저 첫번째 원소인 3의 인덱스 0 이 스택에 들어간다.

 

<2>

그 다음 원소는 5이다.

스택에 있는 인덱스 idx에 대하여 A[idx] < 5 이면 pop하여 res[idx] = 5 를 대입한다.

현 시점에서 스택에 남아 있는 인덱스는 0 하나이고, A[0] = 3 은 5보다 작으므로 pop해주고, res[0] = 5 를 대입한다.

즉, 수열 A의 원소 A[0] 의 오큰수는 5가 된다. 

그리고 5의 인덱스인 1을 스택에 push 한다.

 

<3>

그 다음 원소는 2이다.

현 시점에서 스택에 남아 있는 인덱스는 1이고, A[1] = 5는 2보다 크기 때문에 아무것도 pop하지 않는다.

그리고 2의 인덱스인 2를 스택에 push 한다.

 

<4>

그 다음 마지막 원소는 7이다.

현 시점에서 스택에 남아 있는 인덱스는 1과 2 이다. 스택의 top부터 보면, A[2] = 2는 7보다 작으므로 pop한다.

그리고 A[2] 의 오큰수가 7이 되므로, res[2] = 7 로 갱신한다. 그 다음 인덱스는 1 이고, A[1] = 5 역시 7보다 작으므로 pop한다. A[1] 또한 오큰수가 7이 되므로 res[1] = 7 로 갱신한다.

그리고 7의 인덱스 3을 스택에 push 한다.

 

 

res에는 res[0] = 5, res[1] = 7, res[2] =7, res[3] = -1 이 남아있게 되고, 각각의 원소의 오큰수가 된다.

 

 

 

소스코드 :