[자바] 백준 2548 - 대표 자연수 (java)

 문제 : boj2548

---

 

필요 알고리즘 개념

• 정렬
  
  • 데이터를 정렬하는 방법을 알아야 한다.
• 누적합
  
  • 누적합을 사용해 이 문제를 풀 수 있다.
• 수학 - 중앙값(median)
  • 누적합을 사용하지 않고, 수학의 중앙값 개념으로도 이 문제를 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이1 : 누적합 + 카운팅 정렬을 이용한 풀이법

  cnt[x]를 입력으로 주어진 N개의 수(1~10000)에 대해, x가 입력으로 들어온 횟수라고 하자. sum[x]는 마찬가지로 x가 들어왔던 총 합계이다. 즉, cnt[3] = 4라면 3이 4번 들어왔으므로, sum[3] = 3x4 = 12가 된다.

 

  이렇게 봤을 때, 결국 이 문제에서 제시된 값을 구하는 로직은 다음과 같다.

1. x를 1부터 10000까지 증가시키면서 cnt[x]가 0이 아니라면 (=한번이라도 들어왔던 값이라면) 2번을 진행한다.

2. 그럼 다음과 같이 생각할 수 있다.

- x보다 큰 값들과 x의 차이 = sum[x+1]부터 sum[10000]까지의 합 - x * (cnt[x+1]부터 cnt[10000]까지의 합)

- x보다 작은 값들과 x의 차이 = x * (cnt[1] 부터 cnt[x-1]까지의 합) - sum[1]부터 sum[x-1] 까지의 합 까지의 합

따라서 위 둘을 합치면 x를 선택했을 때의 '차이들의 합'을 알 수 있다.

3. '2'에서 계산된 차이 중 가장 작은 것을 출력해주면 된다.

 

  그리고, '2'에서 보면 부분합을 필요로 한다.따라서 미리 cnt[x]와 sum[x]에 대해 누적합 알고리즘을 적용시켜 둔다면 특정 부분합을 O(1)로 알 수 있다. 누적합 알고리즘을 모른다면 이 글을 참고하자.

 

  전체적으로 시간복잡도를 보면, 카운팅 정렬 및 누적합 전처리에 O(N)이고, 입력된 수의 최대값이 Q라고 할 때(최악의 경우 10000) 이후 O(Q)로 원하는 값을 얻을 수 있다. 최종적으로 O(N+Q) 이다.

 

 

풀이 2 : 정렬 + 수학(중앙값)을 이용한 풀이법

  더 간편한 풀이도 있다. 사실 이 문제는 각 값에 대해 차이의 최소를 찾는 것이므로 단순히 정렬 후, 중앙값(=중위수 =median)만 출력해주면 된다!

 

  이 경우 O(NlogN)이 필요하다. 의외로 풀이 1 쪽이 시간복잡도 상으론 더 이득이고, 실제로도 풀이 1쪽이 약간 더 빠르다.

 

---

 

코드(누적합) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int LIMIT = 10000;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] sum = new int[LIMIT+1];
        int[] cnt = new int[LIMIT+1];
        for (int i = 1; i <= n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            sum[cur]+=cur;
            cnt[cur]++;
        }
        for (int i = 1; i <= LIMIT; i++) {
            sum[i] += sum[i-1];
            cnt[i] += cnt[i-1];
        }
        int min = Integer.MAX_VALUE;
        int answer = 0;
        for (int i = 1; i <= LIMIT; i++) {
            if (cnt[i]-cnt[i-1] == 0) continue;
            int calc = (i*cnt[i-1]-sum[i-1])+(sum[LIMIT]-sum[i]-i*(cnt[LIMIT]-cnt[i]));
            if (min > calc) {
                min = calc;
                answer = i;
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

코드(수학) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] cnt = new int[10001];
        for (int i = 0; i < n; i++) cnt[Integer.parseInt(st.nextToken())]++;
        int tmp = 0;
        int mid = (n-1)/2;
        for (int i = 1; i <= 10000; i++) {
            tmp+=cnt[i];
            if (tmp>mid) {
                System.out.println(i);
                return;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}