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

안녕하세요 파라매트릭 서치 2110 풀다가 오답처리된 코드에 궁금한 점 생겨 질문드립니다.

• 정답처리된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P2110 {
    static int N, C;
    static long result;
    static int[] home;
    static long parametricSearch() {
        long left=0;
        long right=home[N-1]-home[0];
        long mid = (left+right)/2;
        while(left<=right) {
            if(isPossible(mid)) {
                left = mid+1;
                result = mid;
            } else {
                right = mid-1;
            }
            mid = (left+right)/2;
        }
        return result;
    }
    static boolean isPossible(long mid) {
        //그리디한판단 : 맨 첫번째를 두는게 이득 + 거리 mid만큼 떨어진 바로 다음 집에 두는게 이득
        int cnt=1;
        int lastIdx=0;
        for (int i = 1; i < N ; i++) {
            if(home[i]-home[lastIdx]>=mid) {
                lastIdx=i;
                cnt++;
            }
        }
        return C<=cnt;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        home = new int[N];
        for (int i = 0; i < N; i++) home[i] = Integer.parseInt(br.readLine());

        Arrays.sort(home);
        System.out.println(parametricSearch());
    }
}

• 75%에서 오답처리된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P2110 {
    static int N, C;
    static long result;
    static int[] home;
    static long parametricSearch() {
        long left=0;
        long right=home[N-1]-home[0];
        long mid = (left+right)/2;
        while(left<=right) {
            if(isPossible(mid)) {
                left = mid+1;
                result = mid;
            } else {
                right = mid-1;
            }
            mid = (left+right)/2;
        }
        return result;
    }
    static boolean isPossible(long mid) {
        //그리디한판단 : 맨 첫번째를 두는게 이득 + 거리 mid만큼 떨어진 바로 다음 집에 두는게 이득
        int cnt=1;
        int lastIdx=0;
        for (int i = 1; i < N ; i++) {
            if(home[i]-home[lastIdx]>=mid) {
                lastIdx=i;
                cnt++;
            }
            if(cnt==C) return true;
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        home = new int[N];
        for (int i = 0; i < N; i++) home[i] = Integer.parseInt(br.readLine());

        Arrays.sort(home);
        System.out.println(parametricSearch());
    }
}

다른 부분은 전부 동일하고

최소거리가 mid일 때 공유기 C개를 두는 것이 가능한지 판별하는 isPossible 내부에서 return만 다릅니다.

for (int i = 1; i < N ; i++) {
    if(home[i]-home[lastIdx]>=mid) {
        lastIdx=i;
        cnt++;
    }
    if(cnt==C) return true;
}
return false;

설치할때마다 cnt를 증가시키고, cnt==C가 되는 시점에 도달하면 어차피 현재의 mid로 공유기 C개를 두는게 가능하단 의미니까 true를 리턴해서 끝내고, cnt==C에 도달하지 못한다면 C보다 적은 개수만 설치할 수 있으니 false를 리턴한다고 작성했습니다.

반면에 강의안으로 제공해주신 코드에서는 반복문 안에서 판단해서 리턴하는 것이 아니라, 반복문 전부 돈 결과인 cnt와 C를 비교해서 리턴하는 것으로 이해했습니다.

정답풀이가 맞는 방식이라는 점은 이해가 가는데 오답풀이가 어떤 반례가 있는지는 잘 모르겠습니다