빠에야는 개발중

공항 건설하기 본문

공부/알고리즘 문제

공항 건설하기

빠에야좋아 2018. 3. 11. 13:06

1보다 큰 N개의 도시 중 한 곳에 공항을 지을 예정입니다. 사람들의 편의를 위해 공항으로부터 각 사람들까지의 도시간 이동 거리가 최소가 되는 도시에 짓기로 하였습니다. 편의상 도시는 일직선상에 놓여있다고 가정하며 좌표의 범위는 음수가 포함됩니다. 또한 좌표는 정렬되어 있지 않습니다. 직선상의 위치와 그 도시에 사는 사람들의 수가 주어질 때, 공항을 지을 도시의 위치를 반환해주는 함수 chooseCity 함수를 완성하세요. 거리가 같은 도시가 2개 이상일 경우 위치가 더 작은 쪽의 도시를 선택하면 됩니다. 예를 들어 다음과 같은 정보의 도시가 있다고 가정해 봅시다.

위치123
인구수523

이 살 경우, 각각의 도시에 공항을 지었을 때의 사람들의 이동 거리는 8, 8, 12 이므로 1번 또는 2번에 지을 수 있지만, 1의 위치가 더 작으므로 1을 반환해주면 됩니다.


어렴풋이 느꼈지만 모든 경우의 수를 구하는 선형적 방법으로는 타임아웃이 날 것 같았다. 하지만 별다른 방법이 생각이 안 나서 그대로 짜보았고 역시나 타임아웃이 났다. 그러고 답을 검색해보니 그냥 전체 인구수의 절반이 넘는 자리를 선택하면 되는 것이라고 한다. 이 정도면 직관을 뛰어 넘어서 넌센스가 아닐까. 그걸 눈치 못챈 내 잘못이지만...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//전부 다 구하기
class Airport {
    public int abs(int a, int b) {
        if (a - b > 0) {
            return a - b;
        } else {
            return b - a;
        }
    }
 
    public int chooseCity(int n, int[][] city) {
        int answer = 0;
        int temp = 2100000000;
        int[][] arr = new int[city.length][city[0].length];
 
        for (int i = 0; i < city.length; i++) {
            arr[i][0] = city[i][0];
        }
 
        for (int i = 0; i < city.length; i++) {
            for (int j = 0; j < city.length; j++) {
                if (i == j) {
                    continue;
                }
                arr[i][1] += abs(city[i][0], city[j][0]) * city[j][1];
                if(temp < arr[i][1]) {
                    break;
                }
            }
            if(temp >= arr[i][1]) {
                if(temp == arr[i][1]) {
                    temp = answer > arr[i][0] ? arr[i][0] : answer;
                } else {
                    temp = arr[i][1];
                    answer = arr[i][0];
                }
            }
        }
 
        return answer;
    }
 
    public static void main(String[] args) {
        Airport test = new Airport();
        int tn = 3;
        int[][] tcity = { { 1, 5 }, { 2, 2 }, { 3, 3 } };
        System.out.println(test.chooseCity(tn, tcity));
    }
}
 
//절반이 넘으면 종료
class Airport {
    public int chooseCity(int n, int[][] city) {
        int answer = 0;
        int sum = 0;
        int temp = 0;
        for(int i = 0;i<city.length;i++) {
            sum+=city[i][1];
        }
        
        for(int i = 0;i<city.length;i++) {
            temp+=city[i][1];
            if(temp >= sum/2) {
                answer = city[i][0];
                break;
            }
        }
        
        return answer;
    }
 
    public static void main(String[] args) {
        Airport test = new Airport();
        int tn = 3;
        int[][] tcity = { { 1, 5 }, { 2, 2 }, { 3, 3 } };
        System.out.println(test.chooseCity(tn, tcity));
    }
}
cs


'공부 > 알고리즘 문제' 카테고리의 다른 글

124나라의 숫자  (0) 2018.03.12
땅따먹기  (0) 2018.03.11
가장 큰 정사각형 찾기  (0) 2018.03.10
최고의 집합  (0) 2018.03.09
숫자의 표현  (0) 2018.03.08
'공부/알고리즘 문제' Related Articles more
Comments