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

1. 채점사이트에서 출력은 "첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요." 라고 되어 있었습니다.

2. 제 생각대로라면 말들이 여러마리니까 가장 가까운 말들의 거리가 말들마다 다를수도 있겠다는 생각이 들어. 최대거리를 구하기 위해 코드를 조금 다르게 쳤습니다.

    

3. 채점사이트에서는 정답처리 되었는데 확신이 안들어서 이 방식대로 풀어도 되는지 피드백주세요. 또한, 제가 한 방식과 원래 풀이가 어떤 차이가 있는지 궁금합니다.

• 첨부

• 1. 원래 풀이, 내가 생각한 풀이

• 2. 문제 전체 소스코드

   

*강의 풀이 방식 count()

public int count(int[]arr, int distance){
    int ep=0, cnt=1;
    for(int i=1; i<arr.length; i++){
        //배치가능
        if(arr[i]-arr[ep] >= distance){
            cnt++;
            ep=i;
        }
    }
    return  cnt;
}

*내가 푼 방식 count()

public int[] count(int[]arr, int distance){
    int [] res = new int[2];
    int ep=0, cnt=1;
    int min = Integer.MAX_VALUE;
    for(int i=1; i<arr.length; i++){
        //배치가능
        if(arr[i]-arr[ep] >= distance){
            cnt++;
            min = Math.min(min,arr[i]-arr[ep]); // 말들의 최소거리
            ep=i;
        }
    }
    res[0] = cnt; // distance로 배치되는 말의 수
    res[1] = min; // 말들의 최소 거리
    return  res;
}

*강의 풀이 방식 solution()내부 이진탐색 while문

while (lt<=rt){
    int mid = (lt+rt) / 2;
    //mid최소거리만큼 배치했을때 m보다 더 배치할 수 있으므로 거리를 늘린다.
    if(count(arr,mid) >= m){ // mid : 말들의 최소거리
        lt = mid+1;
        answer = mid;
    }
    else rt = mid-1;
}

*내가 푼 solution()내부 이진탐색 while문

while (lt<=rt){
    int mid = (lt+rt) / 2;
    int res[] = count(arr,mid);
    //mid최소거리만큼 배치했을때 m보다 더 배치할 수 있으므로 거리를 늘린다.
    if(res[0] >= m){ // mid : 말들의 최소거리
        lt = mid+1;
        answer = res[1]; // answer = mid 가 아닌 count메소드에서 계산한 말들의 최소거리를 넣어준다.
        //(말들이 여러마리일때 가장 가까운말의 최대거리를 구하라고 문제에 명시되어있어서)
    }
    else rt = mid-1;
}

• 전체 소스코드

import java.util.*;
public class Main {
    public int[] count(int[]arr, int distance){
        int [] res = new int[2];
        int ep=0, cnt=1;
        int min = Integer.MAX_VALUE;
        for(int i=1; i<arr.length; i++){
            //배치가능
            if(arr[i]-arr[ep] >= distance){
                cnt++;
                min = Math.min(min,arr[i]-arr[ep]); // 말들의 최소거리
                ep=i;
            }
        }
        res[0] = cnt; // distance로 배치되는 말의 수
        res[1] = min; // 말들의 최소 거리
        return  res;
    }
    public int solution(int n ,int m, int[] arr){
        int answer = 0;
        Arrays.sort(arr);
        int lt = 1;
        int rt = arr[n-1]-arr[0]; //arr[arr.length-1]로 끝내도 큰 차이 없음
        while (lt<=rt){
            int mid = (lt+rt) / 2;
            int res[] = count(arr,mid);
            //mid최소거리만큼 배치했을때 m보다 더 배치할 수 있으므로 거리를 늘린다.
            if(res[0] >= m){ // mid : 말들의 최소거리
                lt = mid+1;
                answer = res[1]; // answer = mid 가 아닌 count메소드에서 계산한 말들의 최소거리를 넣어준다.
                //(말들이 여러마리일때 가장 가까운말의 최대거리를 구하라고 문제에 명시되어있어서)
            }
            else rt = mid-1;
        }
        return answer;
    }
    public static void main(String[] args) {
        Main M = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int [] arr = new int [n];
        for(int i=0;i<n;i++)arr[i]= kb.nextInt();
        System.out.print(M.solution(n,m,arr));
    }
}