[Java] 프로그래머스 / 퍼즐 게임 챌린지

퍼즐 게임 챌린지

문제

---

문제 설명

일단 문제가 굉장히 길어서 읽기가 싫었는데 요약을 하자면 문제의 난이도와 푸는 시간이 주어진다.
내 수준인 level이 문제의 난이도보다 높다면 그냥 푸는 시간만큼 걸리고 내 level이 문제의 난이도보다 낮다면 전 문제를 다시 풀고 이번 문제를 다시 푸는 작업을 내 level과 문제의 난이도의 차 만큼 반복한다.

내 level과 문제의 난이도의 차 만큼 반복해서 풀었다면 이제 해당 문제를 풀 수 있다.

그렇게 해서 걸리는 최종 시간이 limit 전에 나올 수 있게 나의 level의 최솟값을 정하는 문제이다.

---

구현

처음 생각한 건 당연히 브루트 포스였다. 근데 아무리 생각해도 무조건 시간초과가 날것도 같고 설마 문제를 그렇게 멍청하게 level 의 범위가 100,000 인데 그렇게 냈을리는 없다 생각하고 이분 탐색으로 방향을 바꿨다.

만약에 브루트포스로 푼다면 level이 1부터 시작해서 하기 때문에 최악의 경우 100,000 까지 탐색하고 각 level마다 n개의 퍼즐을 순회해야 하기 때문에 O(D * N) 이니깐 3 * 10^10 이 나온다.

이분탐색으로 하게 된다면 이분탐색은 log2D 만큼 필요하고 n개의 퍼즐 순회는 그대로 하기 때문에 O(logD * N) 이니깐 약 5.1 * 10^6 으로 빠르게 풀 수 있다.

일단 왼쪽 변수 left를 1로, 오른쪽 변수 right를 문제 난이도의 최대 범위인 100,000으로 초기화한다.

그리고 left <= right 의 조건을 가진 while문 내에서 문제를 제한 시간 내에 풀 수 있는지 없는지 확인하는 함수인 canSolve를 구현하였다.

만약에 풀수 있다고 하면 answer를 mid로 초기화 하고 이거보다 더 작은 값이 있을 수 있으니 right를 mid - 1로 다시 초기화 한다.

풀 수 없으면 left를 mid + 1로 초기화하면 된다.

while (left <= right) {
	int mid = (left + right) / 2;

	if (canSolve(diffs, times, mid, limit)) {
		answer = mid;
		right = mid - 1;
	} else {
		left = mid + 1;
	}
}

canSolve 함수에서는 내 level에 따라서 시간이 얼마나 걸리는지 확인해주어야 한다.

시간은 범위가 10^15 까지이기 때문에 long 타입 변수로 선언을 해주고 문제들을 하나하나 확인한다.

문제 조건대로 만약에 문제의 난이도가 내 level보다 작거나 같다면 그냥 걸리는 시간들을 더해주고 그렇지 않다면 재시도를 해주어야 한다.

재시도를 하는 변수를 retry = diffs[i] - level 로 선언해두고 만약에 이번이 첫문제라면 이전 문제가 없기 때문에 이번 문제를 다시 풀어야한다.

첫문제가 아니라면 전 문제를 다시 풀고 이번 문제를 다시 푸는 조건을 넣어주면 된다.

그리고 계산을 한 time이 limit보다 크면 false를 리턴하고 아니면 time <= limit 을 리턴해준다.

private boolean canSolve(int[] diffs, int[] times, int level, long limit) {
	long time = 0;

	for (int i = 0; i < diffs.length; i++) {
		if (diffs[i] <= level) {
			time += times[i];
		} else {
			int retry = diffs[i] - level;
			if (i == 0) {
				time += (long) retry * times[0] + times[0];
			} else {
				time += (long) retry * (times[i - 1] + times[i]) + times[i];
			}

			if (time > limit)
				return false;
			}
		}
	return time <= limit;
}

---

코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int left = 1;
        int right = 100000;
        int answer = right;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (canSolve(diffs, times, mid, limit)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return answer;
    }

    private boolean canSolve(int[] diffs, int[] times, int level, long limit) {
        long time = 0;

        for (int i = 0; i < diffs.length; i++) {
            if (diffs[i] <= level) {
                time += times[i];
            } else {
                int retry = diffs[i] - level;
                if (i == 0) {
                    time += (long) retry * times[0] + times[0];
                } else {
                    time += (long) retry * (times[i - 1] + times[i]) + times[i];
                }

                if (time > limit)
                    return false;
            }
        }

        return time <= limit;
    }
}