[백준 17299] 오등큰수 (Java)

문제 링크: https://www.acmicpc.net/problem/17299

17299번: 오등큰수

1. 주의할 점

- StringBuilder를 사용해서 출력하자(하지 않으면 TLE)

- O(N*N)의 시간복잡도를 가지지 않도록 한다

 

2. 구현

- 각 숫자를 Arr[]에 담으면서, 해당 숫자가 몇 번 등장했는지 Cnt[] 배열에 저장한다

- 오른쪽에 위치하면서 가장 가까운 숫자를 담아야 하므로 Arr[]의 뒤부터 탐색한다

- Stack에는 우 → 좌 로 이동하면서 현재 숫자가 등장한 횟수가 Stack의 Top보다 적을 때 추가한다

- 반대의 경우엔 Pop을 수행한다

- 이때, 현재 숫자가 등장한 횟수가 Stack의 가장 아래에 위치한 숫자보다 크다면 Stack을 비운다

- 위 3가지 경우를 고려하며 Ans[] 배열에 정답을 담는다

- StringBuilder를 이용하여 정답을 담고 출력한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int num = Integer.parseInt(br.readLine());
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    
	    //초기화
	    Map<Integer,Integer> map = new HashMap<>();
	    int arr[] = new int[num];
	    int cnt[] = new int[1000001];
	    int ans[] = new int[num];
	    int maxi = -1;
	    Stack<Integer> s = new Stack<>();       //index 넣기
	    
	    for(int i=0;i<num;i++){
	        arr[i] = Integer.parseInt(st.nextToken());
	        cnt[arr[i]]++;
	    }
	    
	    for(int i=num-1;i>=0;i--){
	        int nowCnt = cnt[arr[i]];
	        if(!s.isEmpty() && nowCnt>=maxi) s.clear();
	        while(!s.isEmpty()){
	            int idx = s.peek();
	            if(cnt[arr[idx]]>nowCnt){
	                ans[i] = arr[idx];
	                break;
	            }
	            else s.pop();
	        }
	        maxi = Math.max(maxi,nowCnt);
	        if(s.isEmpty()) ans[i]=-1;
	        s.add(i);
	    }
	    StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++)
			sb.append(ans[i] + " ");
		System.out.println(sb.toString());
	}
}