BOJ 11652 - 카드

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

11652번: 카드

 

1. 아이디어

Int 범위로는 부족하니까 long 자료구조를 사용해야 한다.

 

최빈값을 구해야 하는 문제이다.

정렬의 특성을 생각해보면 같은 정보들은 인접해있다는 것을 알 수 있으므로 이 특성을 이용해 최빈값을 구한다.

 

예를 들어  6 7 2 3 2 6 7 6 의 카드가 주어졌을 때

정렬을 하면 2 2 3 6 6 6 7 7 이 된다.

 

먼저 정렬을 한 후 같은 정보들은 인접해있다는 특성을 이용해 현재 값과 이전의 값이 같으면 cnt++, 다르면 다시 1부터 cnt 해주는 방식으로 구한다. 

// 정렬
Arrays.sort(num,1, N+1);

// 최빈값 구하기
max = num[1];
current_Cnt = 1;
max_Cnt = 1;

// 2번째 원소부터 N번째 원소까지 같은 숫자가 이어서 나오는지 새로운 수인지 판단
for (int i = 2; i <= N; i++) {
    if (num[i] == num[i - 1]) {
        current_Cnt++;
    } else {
        current_Cnt = 1;
    }

    if (max_Cnt < current_Cnt) {
        max_Cnt = current_Cnt;
        max = num[i];
    }

}

 

2. 시간복잡도

정렬할 때 O(N log N)이고 최빈값 구할 때 O(N)이다.

N의 최댓값이 10만이니까 1초안에 가능하다.

 

3. 구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, current_Cnt, max_Cnt;
    static long[] num;
    static long max;

    public static void main(String[] args) throws IOException {
        input();

        pro();

        bw.write(max+" ");

        bw.close();
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        num = new long[N + 1];

        for (int i = 1; i <= N; i++) {
            num[i] = Long.parseLong(br.readLine());
        }
    }

    static void pro() throws IOException {
        // 정렬
        Arrays.sort(num,1, N+1);

        // 최빈값 구하기
        max = num[1];
        current_Cnt = 1;
        max_Cnt = 1;

        // 2번째 원소부터 N번째 원소까지 같은 숫자가 이어서 나오는지 새로운 수인지 판단
        for (int i = 2; i <= N; i++) {
            if (num[i] == num[i - 1]) {
                current_Cnt++;
            } else {
                current_Cnt = 1;
            }

            if (max_Cnt < current_Cnt) {
                max_Cnt = current_Cnt;
                max = num[i];
            }

        }
    }
}