[알고리즘] 항상 효율적인 코드를 작성하자.

 

 

 

백준 알고리즘 2869번 문제를 풀게 되었다.

사실, 문제만 보면 아주 간단한 문제이다. 그런데 정답 비율이 31%밖에 되질 않는다.

 

의문을 가지며 빠르게 아래 코드를 작성하고 제출해 보았다.

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        int day = 1;
        int h = 0;

        while (true) {
            h += A;
            if (h >= V) {
                break;
            }
            h -= B;

            day++;
        }

        System.out.println(day);
    }
}

 

나름대로 시간을 줄이겠다고 BufferedReader를 사용했음에도 불구하고 시간초과로 오답처리 되었다.

 

위 코드의 시간복잡도는 O( V/(A-B) )이다. V값 즉, 높이값이 매우 크고 A-B가 아주 작으면 반복 횟수는 아주 많아질 것이다.

 

코드를 개선하기 위해 여러 방법을 생각해 본 결과, 수학적으로 접근하면 반복문을 사용하지 않아도 될 것이라는 결론에 도달하여 아래처럼 코드를 작성했다.

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        int up = A - B; // 하루에 올라가는 높이
        int goal = V - B; // 최종 목적지 (마지막 날 낮동안 정상에 도달하면 B만큼 내려갈 필요가 없다.)
        int day = 0; // 총 걸리는 일 수

        if (goal % up == 0) {
            day = goal / up;
        } else { // 정상에 도달하지 못하면 다음날 낮동안 한번 더 이동
            day = goal / up + 1;
        }

        System.out.println(day);
    }
}

 

이렇게 제출하니 제한시간 이내로 코드를 수행할 수 있었다.

 

위 코드는 단순 수학 계산과 조건문만 존재하기 때문에 V, A, B 값에 영향을 받지 않기 때문에 시간복잡도는 O( 1 )이 된다.

 

 

이 문제를 풀며 앞으로 알고리즘 문제를 풀 때 시간제한이 여유롭더라도 최대한 빠르게 수행되도록 코드를 설계하는 습관을 들여야겠다는 생각이 들었다.