[백준_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)이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_17298 {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		Stack<Integer> stack=new Stack<>();
		int n=sc.nextInt();
		int[] num=new int[n];
		
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
		
		for(int i=0;i<n;i++) {
			/*
			 * 스택이 비어있지 않고, 스택에 저장된 인덱스의 배열값(왼쪽) 보다
			 * 오른쪽 배열 값이 크다면 배열 값을 변경해준다. 
			 */
			while(!stack.isEmpty()&&num[stack.peek()]<num[i])
				num[stack.pop()]=num[i];
			// 스택에 해당 인덱스 삽입
			stack.push(i);
		}
		
		/*
		 * 최종적으로 스택에 남아있는 인덱스는
		 * 해당 인덱스의 배열 값 보다 큰 값이 오른쪽에 존재하지 않는다는 의미이기 떄문에
		 * 배열 값을 -1로 변경 
		 */
		while(!stack.isEmpty())
			num[stack.pop()]=-1;
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<n;i++)
			sb.append(num[i]).append(" ");
		
		System.out.println(sb);
	}
}

[고찰]

 해당 문제를 계속 2중 for문으로 시도했더니 시간 초과가 나서 오답 처리를 받았다. 시간 초과가 나지 않기 위해서는 스택의 성질을 이용해야 했지만 이에대한 아이디어가 떠오르지 않아 다른 사람의 포스팅을 참고하여 이해하였다.

 

                                                              <알고리즘>

 예) num = {3,5,2,7}
 num 배열에는 입력받은 숫자를 스택에는 num 배열의 인덱스가 저장된다. 각 과정에서는 해당 인덱스를 스택에 삽입해야 한다. 우선 처음에는 스택이 비었기 때문에 아무런 계산 없이 첫번째 배열의 인덱스(0) 삽입하고 다음 배열의 값으로 넘어간다.

 배열 5에 대한 처리이다. 스택이 비어있지 않기 때문에 스택에서 값을 peek() 한 값(3)과 배열의 값(5)을 비교한다. 스택에서 peek()한 값 보다 배열의 값이 크기 때문에 이는 3의 오큰수가 되므로 스택에서 해당 인덱스(0)을 제거하고 해당 배열의 값에 오큰수 값을 저장한다. 즉, num[0]은 3에서 5로 값이 변경되는 것이다. 이후 5의 인덱스 값인 1을 삽입하고 넘어간다.
  
 다음은 배열 2에 대한 처리이다. 스택에서 peek한 인덱스 1의 값인 5보다 배열의 값인 2가 작기 때문에 이는 5의 오큰수가 될 수 없어 배열 2의 인덱스 2를 삽입하고 넘어간다.
 
 다음은 배열 7에 대한 처리이다. 스택에는 현재 {1,2} 값이 저장되어 있으면 2부터 peek() 된다. 인덱스 2의 배열 값인 2보다 7이 크기 떄문에 배열 값을 7로 바꿔주고, 인덱스 1에 대한 처리도 위와 같다. 마지막으로 스택에 있는 값을 모두 비워냈다면 인덱스 3을 삽입하고 for 문을 종료한다.
  
 결론적으로 스택에 남아있는 인덱스의 의미는 자신보다 오른쪽에 있는 값 중 큰 값이 없다는 것이기 때문에 해당 인덱스의 배열 값을 -1로 바꿔준다. 

 즉, 스택에는 오른수를 구해야 하는 배열 값의 인덱스가 누적되며 저장되고, 스택에서 peek한 값과 그보다 오른쪽에 있는 배열의 값을 비교하여 배열 값이 크다면 해당 오큰수를 peek한 인덱스 배열 값에 복사하는 알고리즘을 반복하는 것이다. 이때 배열 값이 작거나 스택이 비었다면 해당 인덱스를 스택에 저장하고 다음 배열 값으로 넘어간다.  

 

이러한 아이디어를 이해하는데 어려움이 좀 있었지만 위의 과정을 그림을 그려가며 잘 이해한였더니 코드로 옮기는 것은 쉬웠다.