백준 17299 오등큰수 자바[java]

• 오등큰수

17299번: 오등큰수

문제간단설명)

자신보다 오른쪽에 있고, 더 많이 등장한 애들중에 가장 왼쪽에 있는 숫자 출력

 

 

 

풀이)

오큰수 문제에서 이용했던 방식 그대로 썼다.

>참고 이전 포스팅(백준 17298오큰수 자바)

백준 17298 오큰수 java (tistory.com)

각 숫자들이 몇개가 있는지 알수있도록 함수를 만들었다.

이 함수에서는 각 숫자들의 출연개수를 정수형 배열로 반환한다.

>숫자 갯수 세기 하는 방법은 더보기 참고

갯수를 셀 배열 하나를 만든다.

정수형 배열 cnt[] 라고 하자.

이 배열의 크기는 나올 수 있는 가장 큰 숫자 + 1이다.

만약 나올 수 있는 숫자가 1~1,000,000이라면

크기를 1,000,001으로 설정한다.

배열은 인덱스 0부터 시작하므로

cnt[0] 부터 cnt[1,000,000]까지 만들어 질 것이다. (1,000,001개이다)

 

준비 끝

 

숫자를 하나 받아들이면

그 숫자를 인덱스로 가지고 있는 값을 +1 해준다.

 

예를들어 1 1 2 3 3 1 이면

첫번째 값     1이므로 cnt[1]++

두번째 값     1이므로 cnt[1]++

세번째 값     2 이므로 cnt[2]++

네번째 값     3 이므로 cnt[3]++

다섯번째 값 3 이므로 cnt[3]++

여섯번째 값 1이므로 cnt[1]++

 

cnt[]배열에 숫자들이 몇개가 나왔는지 저장되는 것이다.

 

 1이 몇개 나왔는지 알고싶으면 cnt[1]값

n이 몇개 나왔는지 알고싶다면 cnt[N]값 보면 된다.

 

반환한 배열을 cnt[]에 저장했다.

오큰수 문제에서는 그 값들의 크기를 비교했다면,

오등큰수 문제에서는 그 숫자가 얼마나 많이 나왔는지를 비교한다.

그렇기 때문에 전에 짰던 코드에서 cnt[]만 추가해줬다.

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> stk = new Stack<>();
 
        int N = sc.nextInt();
        int seq[] = new int[N];
        int cnt[] = new int[1000001];
        for(int i = 0; i < N; i++){
            seq[i] = sc.nextInt();
        }
        cnt = countNum(seq);
        for(int i = 0; i < seq.length; i++){
 
            while(!stk.isEmpty() && cnt[seq[i]] > cnt[seq[stk.peek()]]){
                seq[stk.pop()] = seq[i];
            }
 
            stk.push(i);
        }
 
        while(!stk.isEmpty()){
            seq[stk.pop()] = -1;
        }
 
        for(int i = 0; i < seq.length; i++){
            bw.write(seq[i] + " ");
        }
        bw.flush();
        bw.close();
    }
 
    public static int[] countNum(int[] tmp){
        int[] cnt = new int[1000001];
 
        for(int i = 0; i < tmp.length; i++){
            cnt[tmp[i]]++;
        }
        return cnt;
    }
}