[Java] 최빈값 알고리즘

Minuuu·2023년 1월 26일

알고리즘

목록 보기

7/36

알고리즘 기초가 부족한 사람이 봤을 때 이해하기 쉽게 작성
단순 구현이 아닌 성능 개선 및 시간복잡도를 고려한 글

1. 문제 설명

전화번호 네자리(0000 ~ 9999)를 입력하여 가장 많은 번호를 찾자

입력형식

가장 첫 줄에 전화번호의 수 N이 1이상 10만 이하의 자연수로 주어진다.
그 후 총 n줄에 걸쳐 전화번호를 입력한다

출력형식

주어진 전화번호 뒷자리들 중 가장 많이 등장한 번호를 출력한다. 0을 포함하여 공백없는 네 자리 숫자로 출력해야한다.
단, 등장한 횟수가 같은 번호가 두 개 이상인 경우 가장 사전순으로 빠른 숫자를 출력한다

2. 알고리즘 접근 방법

배열의 원소들 중 가장 많은 빈도의 값을 Count한다(최빈값)
가장 간단히 생각한다면 반복문을 통해 일일이 비교를 하는 것이다

public static int getFrequentNumber(int[] data, int n) {
        int frequent_num = 0; // 0000~9999 중 가장 많이 등장한 번호
        int max_frequency = 0; // 최고빈도 수

		// 각 번호마다 반복을 통해
        for(int number = 0000; number <= 9999; number++){
            int count = 0;
            // 배열값을 비교한다
            for(int j = 0; j < n; j++){
                if(data[j] == number){
                    count++;
                }
            }
            // 비교후 count수가 최고빈도 수보다 크면
            if(count > max_frequency){
                max_frequency = count;
                frequent_num = number;
            }
        }
        return frequent_num;
    }

위와 같이 코드를 접근한다면 모든 숫자에 대해서 비교하여 값을 도출 할 수 있다
But, 주어진 시간 내에 실행될 수 있을까? 위 코드의 시간복잡도는
0000 ~ 9999 -> 상수 C
j = 0 ~ n까지 -> C * N = O(N)
그러나 상수C가 너무 크기 때문에 생략하지 않으면 O(C*N)
최악의 상황에 C = 10000, N = 10만이라는 문제 조건이 있기에 곱하면 10억 -> 시간제한

3. 시간적 성능 개선

어느 부분이 비효율적일까? 위 코드에서 생각해보면
똑같은 배열[]이 들어있는데 0~ 9999까지 계속 반복해서 순회하는 로직이다(중복순회)
-> 개별 데이터(data[i])의 등장횟수를 구하기 위해 매 번 전체 데이터를 조회하고 있다

반대로 전체 데이터를 한 번 조회하는 과정에서, 각 개별 데이터의 등장 횟수를 구할 순 없을까?

가능하다면, 그런 정보는 변수 하나에 저장할 수 없을 것
why? 대상이 여러개이기 때문이다
-> 공간이 필요하다
-> 어떤 공간에 어떤 기준으로 저장할 것인지 필요
즉 cnt 배열을 정의하고 개별 데이터의 등장 횟수를 구해보자

3 - 1. 배열 활용하기

// table[num] := data배열에서 num이라는 정수가 들어간 횟수
int[] table = new int[10000];

num이 각 전화번호를 나타낸다고하면

전화번호 뒷자리는 항상 0이상의 정수 이니 배열의 인덱스로 활용 가능
전화번호의 경우의 수는 1만개므로, 모든 전화번호에 대해 고유한 칸 생성

빈도수 구하는 것을 반복문 처리가 아닌 위와 같은 배열 처리로 코드를 바꿔보자!

4. 소스코드

import java.util.Scanner;

// 배열 원소 중 가장 많이 등장하는(최빈값)값을 찾아출력하라
// 같은경우 사전 순으로 번호를 출력, 출력 시 4자리 수로 출력(첫자리가 없으면 0123)
public class Q3A {
    public static final Scanner sc = new Scanner(System.in);
    public static final int MAX_TABLE_LENGTH = 10000;

    public static void fillFrequencyTable(int[] data, int n, int[] table) {
        for(int i = 0; i < n; i++){
            // data[i] = data에 저장된 모든 전화번호가 차례로 한번 씩 등장하는 변수
            table[data[i]]++; // table[num] := data배열에서 num이라는 정수가 들어간 횟수
        }
    }

    public static int getFrequentNumber(int[] data, int n) {
        int frequent_number = 0;  //0000~9999중  가장 많이 등장한 번호
        int[] table = new int[MAX_TABLE_LENGTH]; // 0~ 9999까지의 배열(인덱스로 활용한다)
        fillFrequencyTable(data, n, table);

        // table[number]가 가장 큰 number를 frequent_number에 저장하는 로직
        for(int number = 0; number < 10000; number++){
            int count = table[number];
            if(count > table[frequent_number]){
                frequent_number = number;
            }
        }
        return frequent_number;
    }
    public static void main(String[] args) {
        int n = sc.nextInt(); // 입력 수
        int[] data = new int[n]; // 최빈값 비교 데이터 배열 선언
        for (int i = 0; i < n; i++) {
            data[i] = sc.nextInt(); // 비교 데이터 입력
        }

        int answer = getFrequentNumber(data, n);
        System.out.printf("%04d", answer);
    }
}