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

코딩테스트 연습 - 퍼즐 게임 챌린지 문제 바로가기

문제 설명

해결 방법

숙련도의 최솟값을 찾아야 하므로 탐색 알고리즘을 이용하고자 하였습니다.

처음 사용한 탐색 알고리즘은 순차 탐색이였습니다.
순차 탐색은 \(O(N)\) 이라는 시간 복잡도를 갖지만, diffs 의 원소는 100’000 이하이므로
제한 시간 내 풀이가 가능하다고 판단하여 선택하게 되었습니다.

첫 번째 시도 (시간 초과)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = *max_element(diffs.begin(), diffs.end());
    
    while(0 < answer) {
        long long total_time = 0;
        for(int i = 0; i < diffs.size(); ++i) {
            if(diffs[i] <= answer) {
                total_time += times[i];
            }
            else if(diffs[i] > answer && i > 0) {
                total_time += (diffs[i] - answer)
                    * (times[i] + times[i - 1]) + times[i];
            }
        }
        if(total_time < limit) {
            answer -= 1;
        } else if(total_time == limit) {
            break;
        } else {
            answer += 1;
            break;
        }
    }
    return answer;
}

그러나 이 코드는 시간 초과로 인해서 오답처리가 되었습니다.
최소 레벨을 찾기 위해서 순차 탐색 뿐만 아니라 레벨에 따른 문제 풀이 시간 또한 확인해야 하기 때문에
diffs 배열을 매번 순회하여 연산을 해줘야 합니다.

answer 에 저장된 값이 100’000 이고 diffs 의 길이가 300’000 일때, 정답이 1인 경우
제한 시간 내 풀이가 불가능합니다.

두 번째 시도 (정답)

특정 숙련도를 선택하였을 때, 그 숙련도가 적절한지 판단하는 연산은 필수적이므로
기존 순차 탐색이 아니라 이진(이분) 탐색을 이용해 탐색하고자 하였습니다.

#include <string>
#include <vector>

using namespace std;

long long limit_temp;
vector<int> diffs_temp;
vector<int> times_temp;

bool is_minimum_level(int mid) {
    long long total_time = times_temp[0];
    for(int i = 1; i < diffs_temp.size(); ++i) {
        if(diffs_temp[i] <= mid) {
            total_time += times_temp[i];
        }
        else if(diffs_temp[i] > mid) {
            total_time += (diffs_temp[i] - mid)
            * (times_temp[i] + times_temp[i - 1]) + times_temp[i];
        }
        
        if(total_time > limit_temp) {
            return false;
        }
    }
    return true;
}

int solution(vector<int> diffs, vector<int> times, long long limit) {
    diffs_temp = diffs;
    times_temp = times;
    limit_temp = limit;
    
    int left = 1;
    int right = 100'000;
    
    if(is_minimum_level(left)) {
        return 1;
    }

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

        if(is_minimum_level(mid)) {
            right = mid;
        } 
        else {
            left = mid;
        } 
    }
    
    return right;
}

이분 탐색을 사용하기 위해 탐색 범위를 숙련도 범위( \(1 <= (숙련도) <= 100'000\) )로 탐색을 진행했습니다.

추가적으로 숙련도 확인을 위한 연산은 위부 함수로 분리하여 코드를 정리하였습니다.