백준 3011 자바 - 이름 지어주기 (BOJ 3011 JAVA)

문제 : boj3011

 

1.

  A에서 B 구간의 최대가 10^9이므로, 우선 모든 경우를 봐서는 통과할 수 없음을 알 수 있다. 그럼 뭔가 정답 구간을 정할 수 있는 방법이 있다는 얘기이다. 이 문제의 경우, 어떠한 X 지점에 대해 모든 N지점 중 거리의 차가 최소인 지점을 최대한 멀리 두려고 한다(min{|X-Pi|, i ∈ [1,N]}). 즉, X는 모든 N개의 지점 P_i와 최대한 멀리 떨어지면 된다.

 

 

2.

  입력이

4

10 46 56 70

10 70

인 경우를 생각해보자.

 

어떻게 해야 N개의 지점에서 가장 멀리 떨어진 X 지점을 모두 보지 않고 찾을 수 있을까? 최선의 선택은 각 지점들의 중간지점들을 보면, 그 중 가장 양쪽의 차이가 큰 지점을 고르면 될 것임을 생각해볼 수 있다(그리디).

 

그리고 하나 더 생각해볼 수 있는데, A, B의 구간이 위와 같지 않고 그냥 아예 멀리 떨어진 경우를 생각해보자. B가 1000이라고 해보자. 이 경우 따로 생각할 것도 없이 B보자 작은 가장 큰 홀수를 고르면 될 것임을 알 수 있다.

 

 

3.

  그럼 로직은 나왔고, 이걸 구현하면 된다.

내 경우엔 어차피 N이 최대 100밖에 안되므로 최대 99개의 중간지점이 존재할 수 있다. 그럼 '2'의 로직으로 아무리 모든 경우를 봐도 10000번정도만 보면 되므로, 로직을 좀 더 간편하게 했다. candidate라는 리스트를 두고 거기에 정답 후보가 될 수 있는 지점의 위치를 넣은 후 brute force로 후보들 모두에 대해 실제 min{|X-Pi|, i ∈ [1,N]} 를 구해봐서 그중 가장 큰 값을 선택했다.

 

3.1 A보다 크면서 가장 작은 홀수를 candidate에 추가

 

3.2 B보다 작으면서 가장 큰 홀수를 candidate에 추가

 

3.3 N개의 P들을 정렬한 후 각 지점들의 중심지점을 candidate에 추가 ([A, B] 사이의 지점들만)

 

3.4 candidate에 포함된 모든 지점들(최대 101개) 각각에 대해 N개의 지점들의 거리를 구해 정답 구함

 

총 시간 복잡도는 O(NlogN+N^2) 이고 N이 최대 100이므로 문제없이 가능하다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;

public class Main extends FastInput {
    private boolean isOdd(int x) {
        return (x&1)==1;
    }

    private void solution() throws Exception {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = nextInt();
        int a = nextInt();
        int b = nextInt();
        if (a == b) {
            System.out.println(a);
            return;
        }
        Arrays.sort(arr);

        ArrayList<Integer> candidate = new ArrayList<>();
        candidate.add(isOdd(a)?a:a+1);
        candidate.add(isOdd(b)?b:b-1);
        for (int i = 1; i < n; i++) {
            int tmp = arr[i-1]+(arr[i]-arr[i-1])/2;
            if (isOdd(tmp)) {
                if (a <= tmp && tmp <= b)
                    candidate.add(tmp);
            } else {
                if (a <= tmp-1 && tmp-1 <= b)
                    candidate.add(tmp-1);
                if (a <= tmp+1 && tmp+1 <= b)
                    candidate.add(tmp+1);
            }
        }

        int maxMin = 0;
        int answer = 0;
        for (int i = 0; i < candidate.size(); i++) {
            int min = Integer.MAX_VALUE;
            int cur = candidate.get(i);
            for (int j = 0; j < n; j++) {
                min = Math.min(min, Math.abs(cur-arr[j]));
            }
            if (maxMin < min) {
                maxMin = min;
                answer = cur;
            }
        }
        System.out.println(answer);
    }

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

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}