[Programmers] PCCP 기출문제 2번 - 퍼즐 게임 챌린지 - Java

문제

프로그래머스

 

풀이

어떤 퍼즐의 난이도와 사람의 숙련도를 통해 퍼즐을 해결하려고 한다.

퍼즐을 해결하는데 걸리는 시간이 있는데, 그 시간을 제한시간(limit)이내에 완료하는 사람의 숙련도의 최솟값을 구하는 문제이다.

 

퍼즐의 난이도는 30만개의 데이터가 있고, 숙련도는 10만개의 데이터가 나올 수 있다.

여기에서 숙련도를 1부터 10만까지 보면서 퍼즐을 제한시간 이내에 해결할 수 있을까? 라는 것을 생각해보면, 시간초과가 난다.

 

그러면 어떻게 이 문제를 해결할 수 있을까?

=> 바로 이분 탐색이다!! (O(logN))

 

숙련도가 어느 값이 제한 시간 이내에 들어올지 알 수 없으므로, 1부터 최대숙련도 + 1값 중에서 범위를 좁혀가면된다.

숙련도가 mid일때, 제한 시간 이내에, 퍼즐을 맞출 수 있어? 

있으면 숙련도를 낮추고 한번 더 본다.

없으면 숙련도를 높히고 한번 더 본다.

이런 느낌이다.

 

1. 이분 탐색의 mid 값을 구한다.(mid 라는 숙련도라면 퍼즐을 제한시간 이내에 맞출 수 있어?)

 

1-1. 제한시간 이내에 맞출 수 있으면(check를 수행해서 true가 반환 되었을 경우) 숙련도를 낮추고 한번 더 본다.

 

1-2. 제한시간 이내에 맞출 수 없으면(check를 수행해서 false가 반환 되었을 경우) 숙련도를 높이고 한번 더 본다.

 

2. 이분 탐색을 다 수행했다면, 맞추는 숙련도에서 -1이 되었을 것으므로, e는 제한시간에 맞추는 최솟값의 -1일 것이다. 그래서 1을 더해서 반환한다.

 

소스코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        long s = 1;
        long e = limit;

        while (s <= e) {
            long mid = (s + e) / 2;

            if (check(diffs, times, limit, mid)) {
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }            

        return (int) (e + 1);
    }

    private boolean check(int[] diffs, int[] times, long limit, long level) {
        long time_prev = 0;
        int len = diffs.length;

        long sum = 0;

        for (int i = 0; i < len; i++) {
            long diff = (long) diffs[i];
            long time_cur = (long) times[i];

            if (diff <= level) {
                sum += time_cur;
            } else {
                sum += (diff - level) * (time_prev + time_cur);
                sum += time_cur;
            }

            time_prev = time_cur;
        }

        return sum <= limit;
    }
}

 

실행결과

 

자동 형변환

Java 컴파일러의 자동형 변환에 의해서 long값에 int 값을 더해도, 자동으로 long값이 된다는 것을 인식하지 못한채, 모두 형변환을 해서 구현을 해서, 쓸모 없는 long값을 가지고 있다고 생각해, 형변환을 최대한 안하는 방향으로 개선했다.

 

또한, 범위를 limit으로 10^15의 값으로 잡을 필요 없이, 최대 게임 난이도 + 1 값(약 10만)으로 범위를 좁혔다.

 

소스코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int s = 1;
        int e = 100_001;
        
        while (s <= e) {
            int mid = (s + e) / 2;
            
            if (check(diffs, times, limit, mid)) {
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }            
    
        return e + 1;
    }
    
    private boolean check(int[] diffs, int[] times, long limit, int level) {
        int time_prev = 0;
        int len = diffs.length;
        
        long sum = 0;
        
        for (int i = 0; i < len; i++) {
            int diff =  diffs[i];
            int time_cur = times[i];
            
            if (diff <= level) {
                sum += time_cur;
            } else {
                sum += (diff - level) * (time_prev + time_cur);
                sum += time_cur;
            }
            
            time_prev = time_cur;
        }
        
        return sum <= limit;
    }
}

 

실행결과

 

풀이	평균 실행 시간(ms)	평균 메모리 사용량(MB)
long타입 형 변환 수행 + 범위 10^15	14.35	95.60
형 변환 제거 + 범위 10 ^ 6	6.45	94.88

 

개선 결과

평균 실행 시간을 약 2.22배 개선해 코드 성능을 높혔다.