백준 - 대표 자연수

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2548

[문제 설명]

모든 수와 차의 합이 가장 작은 숫자를 고르시오.

 

[접근 방법]

이게 왜 완전탐색 카테고리에 있는지 잘 모르겠다. 

완전탐색 카테고리라서 모든 경우의 수를 따지는 N^2을 생각해봤는데, N은 1 이상 20,000이하다.

즉, 최대 연산횟수는 20,000^2 = 400,000,000 => 4억이다.

1초 1억이라고 단순 계산해도 4초는 걸린다. 따라서 이와 같이 풀면 안된다.

 

그렇다면 규칙이 있을 텐데 무엇일까? 수학적인 분석은 아니지만, 나는 이를 숫자 간의 거리라고 생각했다.

우리가 친구들이랑 만날 때 가운데 지점에서 만나면 각자 가장 가까운 거리에서 만나듯이, 가운데 인덱스에서 만나면 될 거라고 생각했다.

전체 숫자의 개수가 홀수인 경우에는 정확히 가운데 숫자를 가져오도록 했고, 짝수인 경우에는 가운데 두개를 가져오게 했다.

 

[Java 코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfNumbers = Integer.parseInt(br.readLine());
        int[] arrOfNumbers = new int[cntOfNumbers];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < cntOfNumbers; i++) {
            arrOfNumbers[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arrOfNumbers);

        int answer = 0;
        int diffrenceA = getDiffrence(arrOfNumbers, cntOfNumbers/2);
        if (cntOfNumbers % 2 == 0) {
            int diffrenceB = getDiffrence(arrOfNumbers, cntOfNumbers/2-1);
            if (diffrenceB > diffrenceA) {
                answer = arrOfNumbers[cntOfNumbers/2];
            } else {
                answer = arrOfNumbers[cntOfNumbers/2-1];
            }
        } else {
            answer = arrOfNumbers[cntOfNumbers/2];
        }
        System.out.println(answer);
    }

    private static int getDiffrence(int[] arrOfNumbers, int idxOfPivot) {
        int diffrence = 0;
        for (int i = 0; i < arrOfNumbers.length; i++) {
            diffrence += Math.abs(arrOfNumbers[i] - arrOfNumbers[idxOfPivot]);
        }

        return diffrence;
    }
}

 

 

[내 답안 수정하기]

다른 사람들의 답안을 보니까 결국 개수가 짝수개더라도, 앞과 뒤에 차수의 합은 같은 듯하다.

따라서 필요 없는 if문과 계산과정을 제거해줄 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfNumbers = Integer.parseInt(br.readLine());
        int[] arrOfNumbers = new int[cntOfNumbers];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < cntOfNumbers; i++) {
            arrOfNumbers[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arrOfNumbers);

        int answer = 0;
        if (cntOfNumbers % 2 == 0) {
            answer = arrOfNumbers[cntOfNumbers/2-1];
        } else {
            answer = arrOfNumbers[cntOfNumbers/2];
        }
        System.out.println(answer);
    }
}