[JAVA/17299번] 오등큰수

문제

입력 및 출력

풀이

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

class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 수열 A의 크기 N
        int N = Integer.parseInt(br.readLine());

        // 수열 A의 원소를 저장할 배열
        String[] strArray = br.readLine().split(" ");

        // strArray에 저장된 문자열을 숫자로 변경하기 위한 배열 A
        int[] A = new int[strArray.length];

        // A의 배열안에 숫자의 개수를 저장할 배열 F
        int[] F = new int[1000000];

        // strArray의 데이터를 숫자로 변경, F배열에 각 숫자의 인덱스에 맞는 값을 증가
        for (int i = 0; i < strArray.length; i++) {
            A[i] = Integer.parseInt(strArray[i]);
            F[(A[i] - 1)] = F[(A[i] - 1)] + 1;
        }

        // 스택 선언
        Stack < Integer > stack = new Stack < > ();

        // A의 길이만큼 반복문 수행
        for (int i = 0; i < A.length; i++) {
            // 스택이 비어있지 않고, F배열의 인덱스를 비교하여 클 경우 A배열의 데이터를 현재 값으로 변경
            while (!stack.isEmpty() && F[(A[stack.peek()] - 1)] < F[(A[i] - 1)]) {
                A[stack.pop()] = A[i];
            }
            stack.push(i);
        }

        // 그외의 경우 -1저장
        while (!stack.isEmpty()) {
            A[stack.pop()] = -1;
        }

        // 시간초과를 해결하기 위한 StringBuilder선언
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < A.length; i++) {
            sb.append(A[i] + " ");
        }

        // 결과문 출력
        System.out.println(sb);
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법

• 오큰수 문제에서 약간의 변형을 한 문제로, 기존의 문제는 오른쪽에서 자신보다 큰 수 중 왼쪽에 있는 수를 선별하는거라면 이번 문제는 동일한 값의 개수를 파악하여 개수를 비교하는 방법으로 변경되었다.

• 따라서 문제를 풀 때 가장 핵심은 배열F로, A배열의 값을 F배열의 인덱스로 설정함으로써 입력받은 수열의 개수를 파악할 수 있었고 이전 오큰수의 방법과 동일하게 문제를 해결할 수 있었다.