[JAVA][백준] 1090 - 체커

예제 1

4 15 14 15 16 14 15 16 15

0 2 3 4

예제 2

4 1 1 2 1 4 1 9 1

0 1 3 10

예제 3

2 4 7 4 7

0 0

 

강의를 듣는 도중에 나온 문제 처음 접해보는 플레티넘 문제라서 긴장했다 당연(?) 하게도 처음부터 풀이를 해내지는 못했고 풀이를 하는 방법을 듣고 나서 나는 구현만 했다고 생각한다. 

이 문제의 포인트라고 생각하는 부분은

1. x, y 따로 계산해서 더해 최솟값 구하기

2. 입력마다 들어오는 좌표값의 모든 x,y 조합의 좌표를 조사하여야 함

3. 누가 오는지는 상관이 없음  좌표마다 최소거리가 있고 가장 가까운 값을 가져오면 됨

 

해서 구현한 코드다

package online.judge.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 체커 플레티넘4
 * 인프런 알고
 * 미완
 * 1. x,y 따로 계산해서 더해 최솟값 구하기
 * 2. 입력으로 들어오는 좌표값의 x,y 좌표마다 탐색해야 함
 * 3. 좌표마다 최소 거리가 있고 거기서 가장 가까운거 가져오면 됨
 * 4. 누가 올건지 상관이 없음
 */
public class No1090 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Coord> list = new ArrayList<>(); // 좌표값
        Set<Integer> xList = new HashSet<>(); // x좌표 리스트
        Set<Integer> yList = new HashSet<>(); // y좌표 리스트

        int n = Integer.parseInt(br.readLine());

        //입력받기
        for(int i=0;i<n;i++){
            String[] strArr = br.readLine().split(" ");
            list.add(new Coord(Integer.parseInt(strArr[0]),Integer.parseInt(strArr[1])));
            xList.add(Integer.parseInt(strArr[0]));
            yList.add(Integer.parseInt(strArr[1]));
        }

        //좌표 만들기
        List<Coord> distance = new ArrayList<>();
        Object[] xArr = xList.toArray();
        Object[] yArr = yList.toArray();
        for(int i=0;i<xArr.length;i++){
            for(int j=0;j<yArr.length;j++){
                distance.add(new Coord((Integer) xArr[i], (Integer) yArr[j]));
            }
        }

        // 좌표마다 점과의 거리 측정
        for(int i=0;i<distance.size();i++){
            Coord cord = distance.get(i);
            List<Integer> dist = cord.getDistance();
            for(int j=0;j<list.size();j++){
                int x = Math.abs(list.get(j).getX() - cord.getX());
                int y = Math.abs(list.get(j).getY() - cord.getY());
                dist.add(x+y);
            }
            dist.sort(Comparator.naturalOrder());
        }

        //출력
        for(int i=0;i<n;i++){
            int min = 1_000_001 * n;
            for(int j=0;j<distance.size();j++){
                List<Integer> dist = distance.get(j).getDistance();
                int sum = 0;
                for(int k=0;k<=i;k++){
                    sum += dist.get(k);
                }
                if(sum < min){
                    min = sum;
                }
            }
            System.out.println(min);
        }

    }
}
class Coord{
    private int x;
    private int y;
    private List<Integer> distance;

    public Coord(int x, int y) {
        this.x = x;
        this.y = y;
        this.distance = new ArrayList<>();
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
    public List<Integer> getDistance(){
        return distance;
    }

}