[랜덤 마라톤] 표본의 수 구하기(13204)

1. 문제 풀이 아이디어

• 수학적으로 계산하면 문제를 효율적으로 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int t = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < t; i++) {
            double d = Double.parseDouble(bufferedReader.readLine());
            int n = 1;
            while (true) {
                int k = (int) Math.round(d * n / 100);
                double p = Math.round(100000.0 * k / n) / 1000.0;
                if (p == d) {
                    stringBuilder.append(n).append('\n');
                    break;
                }
                n++;
            }
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 수학 공식을 사용해 k 값을 구한 후, 퍼센트를 계산하여 소수 넷째 자리에서 반올림한 값을 입력받은 d와 비교했다. 값이 일치하면 결과를 출력하고, 아니면 n을 증가시키며 반복했다.

4. 이전 코드

ver.1 시간 초과

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int t = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < t; i++) {
            double d = Double.parseDouble(bufferedReader.readLine());
            int n = 1;
            int result = 0;
            while (result == 0) {
                for (int j = 0; j <= n; j++) {
                    double p = Math.round(100000.0 * j / n) / 1000.0;
                    if (p == d) {
                        result = n;
                        break;
                    }
                    if (p > d) {
                        break;
                    }
                }
                n++;
            }
            stringBuilder.append(result).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

• 모든 경우를 하나씩 확인하여 해결하려 했을 때 시간 초과가 발생했다.

ver.2 만족스럽지 못한 속도

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int t = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < t; i++) {
            double d = Double.parseDouble(bufferedReader.readLine());
            int n = 1;
            int result = 0;
            while (result == 0) {
                int l = 0, r = n;
                while (l <= r) {
                    int m = (l + r) / 2;
                    double p = Math.round(100000.0 * m / n) / 1000.0;
                    if (p == d) {
                        result = n;
                        break;
                    }
                    if (p > d) {
                        r = m - 1;
                    } else {
                        l = m + 1;
                    }
                }
                n++;
            }
            stringBuilder.append(result).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

• 이진 검색을 사용해 문제를 해결했을 때 시간 초과는 발생하지 않았지만 속도가 여전히 느렸다.