17298_ <오큰수>

17298번: 오큰수 (acmicpc.net)

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이다.

 

문제 이해는 쉽다. 근데 이걸 코드로 구현하는게 상당히 막막했다. 오른쪽에 있으면서 크면서 가장 왼쪽에 있다. 흠

 

stack을 활용하는 훌륭한 아이디어를 구글링해서 찾았고 정말 기가막히다.

 

결론적으로 index을 스택에다가 넣는 것이다!!

 

근거. 일단 값을 대체해야한다. 오큰수로 대체를 해야하기에 인덱스를 스택에다가 넣고 다루면 변경하기도 쉽다. 그리고 오른쪽 놈에만 관심이 있기에 for문으로 인덱스가 점차 늘어나기에 스택에다가 인덱스 값을 넣는 건 참 좋은아이디어이다

 

알고리즘은 간단하다.

 

일단 기본적으로 모든 인덱스는 스택에 들어간다. 인덱스라 했으니 숫자들은 배열에 넣었겠다.

당연하겠다..? 작든 크든 일단 비교의 대상이기 때문이다. 자신이 바뀔 놈인지 아닌지는 모르기때문이다.

스택에서 차곡차곡 넣었을때, 배열의 다음값보다 스택의 peek값 즉 제일 최신의 스택값이 크다면, 스택의 index peek값을 다음 값으로 바꿔준다. 그리고 pop한다.  

크면서 오른쪽에 있는것들 중 젤 왼쪽이니 큰거 발견한 순간 바로 pop하는게 맞다.

비교당했던 그 배열의 다음값의 인덱스를 다시 스택에 넣어준다. 이녀석보다 큰 녀석이 오른쪽에 있을 가능성도 있기 때문이다.

 

이렇게 반복문이 끝나면 스택에 값이 남아있는지 확인해야겠다. 스택에 값이 남았다면 오큰수가 존재하지 않았다는 말이 되니, -1로 대체해주고 pop시키면 끝!

package 스택과큐;
import java.io.*;

import java.util.*;

public class _17298_오큰수 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<>();
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st =  new StringTokenizer(br.readLine());
		
		for(int i=0; i<n; i++) {
			arr[i]= Integer.parseInt(st.nextToken());
		}
		
		for(int i=0; i<n; i++) {
			
			while(!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
				arr[stack.pop()] = arr[i];
			}
			//기본적으로 위의 while문 조건이 (next element가 전보다 클경우) stack에다가 값을 
			//push해야한다.
			stack.push(i);	
			
		}
		
		//이렇게 for문의 loop가 끝나면 stack에 남은 element가 필연적으로 한개는 생긴다.
		//마지막 element는 for문이 끝나면 pop될 기미가 없으니까.  따라서 이는 -1을 할당해야함
		while(!stack.isEmpty()) {
			arr[stack.pop()] = -1;
		}
	
		
		
		for(int i=0; i<n; i++) {
			sb.append(arr[i]+" ");
		}
		System.out.println(sb);

	}

}