인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

김대영님의 프로필 이미지
김대영

작성한 질문수

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

완탐 1090

해결된 질문

작성

·

319

1

안녕하세요

자바로 강의 듣고 있는 학생입니다.

강의를 들었을 때 이해한 바로는

  1. x,y 따로 계산해서 더해 최솟값을 구한다.

  2. 받은 좌표의 겹치는 부분 그러니까 예제로 보았을 때 x: 14~16 y:14~16의 로 모이는 모든 경우를 찾는다

  3. k번째에 k명이 모이는 최소 이동 횟수를 구하면 되니까 확인한 좌표에서 가까운 k개를 구하면 된다

이렇게 이해하고 구현하면 될까요?

그리고 하루정도 고민한다 해도 해결되지 않는다면 다른사람의 답, 풀이를 확인해봐도 될까요? 아니면 계속해서 시도하는게 좋을까요?

답변 2

1

김대영님의 프로필 이미지
김대영
질문자

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 Main{
    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<>();
        Set<Integer> yList = new HashSet<>();

        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;
    }

}

이렇게 해서 맞긴 맞았네요..

0

코딩 센세님의 프로필 이미지
코딩 센세
지식공유자

저는 너무 혼자서 풀고 싶은 문제가 있을때는 한달이 걸려도 계속 고민하는 경우가 있습니다! 그런 문제가 아니라면

다른 사람의 답 풀이를 본다고 해서 내가 고민하고 노력한 과정이 없어지지 않으니 기간과 상관없이 다른 사람의 정답을 보고 싶을 때에는 보시면 됩니다 ㅎㅎ

김대영님의 프로필 이미지
김대영

작성한 질문수

질문하기