백준 17299 (오등큰수) - java

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

17299번: 오등큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

 

요약

• 인덱스를 기준으로 오른쪽에 있는 수 중 등장 횟수가 더 많은 가장 왼쪽의 수(처음 수)를 저장하는 문제

유형 : 자료구조 (스택)

 

주의

• 스택에 수를 저장할 때 인덱스도 함께 저장해야 한다.
• 수가 저장되지 않은 곳에는 -1을 출력하도록 한다.
• 등장 횟수를 저장하기 위해 처음에는 HashMap을 사용했다. 하지만 배열에 저장해도 충분하고 속도 차이가 어마무시하다....

전체 코드

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

public class Main {

    static int n = 0;
    static int[] board;
    static int[] count = new int[1000001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        board = new int[n+1];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1;i<=n;i++){
            board[i] = Integer.parseInt(st.nextToken());

            count[board[i]] += 1;
        }

        Stack<Node> stack = new Stack<>();

        StringBuilder sb = new StringBuilder();
        int[] result = new int[n+1];
        for(int i=1;i<=n;i++){

            while(!stack.isEmpty()){
                Node tmp = stack.peek();

                if(count[tmp.v] < count[board[i]]){
                    result[tmp.i] = board[i];
                    stack.pop();
                }

                else{
                    break;
                }
            }

            stack.push(new Node(board[i],i));
        }

        for(int i=1;i<=n;i++){
            if(result[i] == 0)
                sb.append(-1+" ");
            else
                sb.append(result[i]+" ");
        }sb.append("\n");

        System.out.print(sb);
        br.close();
    }
}
class Node{
    int v;
    int i;

    Node(int v,int i){
        this.v = v;
        this.i = i;
    }
}