[BOJ-JAVA] 17299번: 오등큰수

문제

https://www.acmicpc.net/problem/17299

17299번: 오등큰수

수열이 주어질 때 각각 인덱스의 수에서 오른쪽에 있는 수 중 가장 개수가 많은 최좌측 수를 구하는 문제이다.

 

 

https://www.acmicpc.net/problem/17298

17298번: 오큰수

오큰수 문제와 상당히 유사한 대신 개수를 사용한다는 점이 다르다.

 

문제풀이 

우선 주어진 수열의 가장 큰수를 이용해 배열을 만들고 개수를 센 후 배열에 저장해둔다. (여기서 index는 각 수를 의미, 저장된 값은 개수)

여기서도 역시나 stack을 이용해서 문제를 해결한다. 수열을 차례로 확인하며 count가 큰 수가 나올 때까지 index를 stack에 push하고, count가 큰 수를 만나면 stack.peek와 비교해가며 값을 count가 큰 수로 변경한다.

https://miraekwak.tistory.com/165

[BOJ-JAVA] 17298번: 오큰수

오큰수 풀이에서 count를 추가한 것이다.

 

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.valueOf(br.readLine());
        String[] line = br.readLine().split(" ");
        int[] arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.valueOf(line[i]);
        }

        int[] count = new int[Arrays.stream(arr).max().getAsInt()+1];
        for(int num: arr) {
            count[num] += 1;
        }

        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<N; i++) {
            while(!stack.empty() && count[arr[i]] > count[arr[stack.peek()]]) {
                arr[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        while(!stack.empty()){
            arr[stack.pop()] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for(int ngf: arr){
            sb.append(ngf).append(' ');
        }
        System.out.println(sb);
    }
}