[백준/Java] 2285번 - 우체국

문제 & 난이도

• 그리디 알고리즘
• 난이도 : 골드 4

 

풀이

 

📄내 알고리즘 풀이

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

public class Beakjoon2285 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        //첫째 줄 : 마을의 수 N
        int N = Integer.parseInt(bf.readLine());

        //배열 생성
        int[][] town = new int[N+1][2];

        //이후 N개의 줄 : 마을의 번호, 해당 마을의 거주민 수
        for(int i = 1; i <= N; i++){
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int index = Integer.parseInt(st.nextToken());
            town[i][0] = index;
            int people = Integer.parseInt(st.nextToken());
            town[i][1] = people;
        }

        //각 케이스마다 거리를 저장할 배열 생성
        int[] distance = new int[N+1];

        //각 케이스마다 거리의 합 계산
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++) {
                if (town[j][0] < i) {
                    distance[i] += (town[j][1] * (i-town[j][0]));
                }
                else if(town[j][0]>i){
                    distance[i] += (town[j][1] * (town[j][0]-i));
                }
                else continue;
            }

        }

        //최소값에 해당하는 인덱스 출력
        int min = distance[1];
        int result=1;
        for(int i = 1; i <= N; i++){
           if(distance[i] < min){
               result = i;
           }
       }

        //결과
        System.out.println(result);

    }
}

 

 

📄정석 풀이

package greedy;

import java.util.*;

//전체 인구의 절반이 넘어가는 index찾기

public class Beakjoon2285_retry {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //첫째 줄 : 마을의 갯수 N
        int N = sc.nextInt();

        //2차원 배열 생성
        int[][] hometown = new int[N][2];

        //그 다음 N개의 줄 - 마을의 인덱스, 구성원 수 배열에 저장하기
        for(int i = 0; i < N; i++) {
            hometown[i][0] = sc.nextInt();
            hometown[i][1] = sc.nextInt();
        }

        //배열 정렬
        //배열a의 0번째 인덱스를 기준으로 오름차순 정렬하겠다는 뜻
        Arrays.sort(hometown, Comparator.comparingInt(a -> a[0]));

        //전체 구성원 수
        int people = 0;
        for(int i = 0; i < N; i++) {
            people += hometown[i][1];
        }

        //중간 지점보다 큰 인덱스
        int middle = (people+1)/2;

        //현재 위치
        int location=0;
        for(int i = 0; i < N; i++) {
            location += hometown[i][1];
            if(location>=middle) {
                System.out.println(hometown[i][0]);
                break;
            }
        }
    }
}

 

 

느낀 점

 

Scanner을 이용해서 풀었는데 메모리 초과가 나서 BufferedReader을 썼는데 시간 초과가 나와서 제출은 실패한 문제. 

지금은 코딩 테스트 준비 초반이라 풀어보는 것을 목적으로 하여 여기까지만 풀어봤다.

 

다른 분들의 풀이를 찾아보니

"그리디 문제 → 정렬 이용"을 이용하여 마을(첫 번째 기준)과 사람(두 번째 기준)을 이용하여 정렬한 뒤, 사람의 총 인원중 가운데번째 있는 사람의 위치에 우체국을 세우면 된다고 한다.