17299 오등큰수 JAVA

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

 

이번 문제는 이전에 풀었던 오큰수와 비슷한 방식으로 접근하여 풀 수 있다.

다만 다른 점은 배열 요소의 값으로 오큰수를 구하는 게 아닌, 등장횟수로 구한다는 것이다.

또한 문제를 풀기 전에, 내가 구현하려는 코드를 간략히 생각이나 글로 정리하고, 시간 복잡도를 계산해보는 습관을 들이기 시작했다.

이번 문제는 각 요소를 모두 탐색하여 빈도수를  구하는 것은 매우 비효율적이고 O(N^2)의 시간 복잡도를 가지게 되는데, 그렇게 되면 이 문제를 절대 해결할 수 없다. 그래서 나는 물론 여러가지 방법이 있겠지만, 나는 이를 구현하기 위해서 해쉬맵을 사용하여, 등장횟수를 구하는 방법을 사용했다.

*시간 복잡도에서 상수는 생략할 수 있다.

 

StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; st.hasMoreTokens(); i++) {
    int num = Integer.parseInt(st.nextToken());
    numArr[i] = num;

    if(map.containsKey(num)) // key를 포함하고 있다면 value + 1
        map.put(num, map.get(num) + 1);

    else { // key가 등록되어 있지 않다면 1을 저장
        map.put(num, 1);
    }
}

위와 같이, 기존에 등록되어 있지 않은 수라면, key로 숫자를, value로 1회 등장하였으니 1을 저장하고,

이미 존재하는 key, 즉 전에 나왔던 숫자일 경우, 해당 key의 value의 값에 1을 더한다.

이렇게 하면, 빈도수를 구할 수 있다.

 

indexStack.push(0);
for(int i = 0; i < N; i++) {

    while(!indexStack.empty() && map.get(numArr[indexStack.peek()]) < map.get(numArr[i]))
        result[indexStack.pop()] = numArr[i];

    indexStack.push(i);
}

인라인으로 적는 걸 좋아해서, 가독성이 조금 떨어지겠지만 약간의 설명을 덧붙이겠다.

나는 앞전의 코드를 통해서 각 key의 모든 빈도수를 구해놨다. 그렇다면 우리가 앞으로 해야할 것은 num의 각 index에 해당하는 값을 key로 하여금 value를 얻어내면 된다. 그리고 비교 대상도 당연히 단순히 numArr[i]가 아닌, key의 값으로 value를 얻어내야 한다.

 

 

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

public class S17299 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] numArr = new int[N], result = new int[N];
        Map<Integer, Integer> map = new HashMap<>(N);
        Stack<Integer> indexStack = new Stack<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; st.hasMoreTokens(); i++) {
            int num = Integer.parseInt(st.nextToken());
            numArr[i] = num;

            if(map.containsKey(num)) // key를 포함하고 있다면 value + 1
                map.put(num, map.get(num) + 1);

            else { // key가 등록되어 있지 않다면 1을 저장
                map.put(num, 1);
            }
        }

        indexStack.push(0);
        for(int i = 0; i < N; i++) {

            while(!indexStack.empty() && map.get(numArr[indexStack.peek()]) < map.get(numArr[i]))
                result[indexStack.pop()] = numArr[i];

            indexStack.push(i);
        }

        indexStack.stream().forEach(i -> {
            result[i] = -1;
        });

        for(int i : result)
            sb.append(i).append(" ");

        System.out.println(sb);
    }
}

이 문제는 아이디어만 떠오르면 어려운 문제도 아니다. 

프로그래밍을 공부한 지 두달 정도밖에 안됐지만, 스스로 구현함에도 불구하고 한달 사이에 푸는 문제의 수준 차이가 정말 달라졌다.

꾸준함은 매우 강력한 무기라고 느낀 하루였다. 앞으로 7월 내에 플래티넘 문제들도 도전하는 더욱 성장한 개발자가 되어야겠다.