17299. <오등큰수>

17299번: 오등큰수 (acmicpc.net)

17299번: 오등큰수

오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미.

 

1. 카운팅 배열

일단 빈도수체크를 해야하는 점. 여기서 카운팅 배열을 하나 만들어 아이디어를 떠오르는 게 좋겠다.

(수의  max range가 100만이니 100만+1짜를 만든다.)

그래서 input을 받고나면 정수 값마다의 인덱스에 자신들의 빈도수가 체크가 되겠다. 

 

2. 스택

스택을 쓰는 근거는 최신 업데이트를 필요로 하기 때문이다. 오른쪽에 있으면서 가장 왼쪽 이란 말은 오등큰수가 있으면 바로 그 값으로 바꿔야하기에 인풋된 값들의 인덱스를 스택에다가 넣는다.

 

여기서 스택에다가 인덱스를 넣는게 아주 중요한 포인트인데 그 이유는

1. 스택에다가 인덱스를 넣어서 최신 업데이트를 빠르게 한다. arr[stack.pop]= 다른 값 을 한줄 적는순간 stack에서 값이 pop되며, arr의 값이 replace되기 때문에 유리하다.

2. loop가 끝나고 난 후 stack에 값이 남았다면 이 값들을 -1로 바꿔야한다. 만약 스택에다가 인덱스를 넣어줬다면 stack.pop을 하면 replace -1로 하기 매우 용이하다.

 

 

예제로 

7

1 1 2 3 4 2 1 이 들어온다면, input을 받는 순간 각각의 정수를 인덱스로 취하는 cnt배열에다가 값을 ++해준다.

그 후

또한 이들을 담을 tmp배열을 생성한다.

 

tmp를 배열을 쭉 돌며 기본적으로 모든 인덱스는 스택에 들어간다.

하지만 그 와중 cnt가 더 큰 즉 빈도수가 더 높은 값이 나온다면, 이 값 이전의 값 (stack.peek())이 이 더 높은 값으로 replace되야 되기 때문에 이를 바로 바꾸고 stack에서 pop을 해준다. 이렇게 된다면 이 전의 값은 빈도수가 더 높은 오등큰수로 바뀌고 pop되지만 그 다음의 peek값이 다음 값보다 클지 작을지 모르기 때문에 while문을 써서 상태를 유지한다.

 

loop가 끝나도 stack에 값이 남았다면 이는 오등큰수가 없다는 뜻이니 -1로 replcae한다.

 

중요한 포인트는, 이 수열의 max range는 100만이다. 따라서 100만번 sysout하면 시간적으로 비효율적이니 stringbuilder로 한번에 해버리자.

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

public class _17299_오등큰수_again {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		//빈도수 카운팅 배열
		int[] cnt = new int[1000001];
		//
		int[] ans = new int[n];
		int[] tmp = new int[n]; 
		//
		Stack<Integer> stack = new Stack<>();
		
		
		for(int i=0; i<n; i++) {
			tmp[i] = Integer.parseInt(st.nextToken());
			cnt[tmp[i]]++;
		}
		
		
		
		
		for(int i=0; i<n; i++) {
			while(!stack.isEmpty() && cnt[tmp[i]] > cnt[tmp[stack.peek()]]) {
				ans[stack.pop()] = tmp[i];
				
			}
			
			//default로 stack에다 인덱스를 push는해야됌
			stack.push(i);
		}
		
		
		//stack이 비지 않았으면 오등큰수는 존재하지 않는다
		//stack에다가 인덱스를 넣어주는 이유 중 큰 이유 .. -1로 마지막에 배열 조작 해야함
		while(!stack.isEmpty()) {
			ans[stack.pop()] = -1;
		}
		
		for(int x : ans) {
			sb.append(x+" ");
		}
		
		System.out.println(sb);
		
		

	}

}