LV2. [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 - 이진(이분)탐색

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=cpp

프로그래머스

---

문제 내용

 

퍼즐의 난이도를 정수로 담은 배열 (diffs[]),

퍼즐 소요 시간이 정수로 있는 배열 (times[])

가 주어질때 , 모든 퍼즐을 풀었을때의 제한시간(limit)안에 풀수있는 숙련도(level)을 반환하기

 

*입력값

diffs 배열 : 퍼즐의 난이도

times 배열 : 퍼즐의 소요시간

limit : 모든 퍼즐을 풀었을때의 제한시간

*출력값

result : 모든 퍼즐을 풀었을때의 최소 숙련도(Level)

 

문제 해결 (코드포함)

문제에서 계산식을 제공해준다.

(현재 퍼즐 소요시간 + 이전 퍼즐 소요시간) * (현재퍼즐 레벨 - 숙련도) + 현재 퍼즐 소요시간 = 해당 숙련도의 퍼즐 소요시간

해당 계산식에서 limit 범위 안에 최소 <숙련도>를 구하는 문제다 .

//(현재 퍼즐 소요시간 + 이전 퍼즐 소요시간) * (현재퍼즐 레벨 - 미지수 숙련도) + 현재 퍼즐 소요시간 = 해당 숙련도의 퍼즐 소요시간 

long long PuzzleSolve(int level, vector<int> diffs, vector<int> times)
{
    long long solveTime = 0;

    for (long long i = 0; i < diffs.size(); i++)
    {
        if (diffs[i] > level)
        {
            solveTime += (times[i] + times[i - 1]) * (diffs[i] - level) + times[i];
        }
        else
        {
            solveTime += times[i];
        }
    }

    return solveTime;
}

우선 해당 계산 수식을 함수로 구현한다.

(long long을 쓴 이유는 limit의 범위 10^15 때문)

 

첫번째 시도

#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

//제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

//(현재 퍼즐 소요시간 + 이전 퍼즐 소요시간) * (현재퍼즐 레벨 - 미지수 숙련도) + 현재 퍼즐 소요시간 = 해당 숙련도의 퍼즐 소요시간 

long long PuzzleSolve(int level, vector<int> diffs, vector<int> times, long long limit)
{
    long long solveTime = 0;

    for (int i = 0; i < diffs.size(); i++)
    {
        if (diffs[i] > level)
        {
            solveTime += (times[i] + times[i - 1]) * (diffs[i] - level) + times[i];
        }
        else
        {
            solveTime += times[i];
        }
    }

    return solveTime;
}

int solution(vector<int> diffs, vector<int> times, long long limit)
{
    int level = 0;
    long long answer;

    do 
    {
        level++;
        answer = PuzzleSolve(level, diffs, times, limit);
    } while (limit < answer);


    return level;
}

 

그리디 문제인줄 알고 , 최솟값 Level(숙련도)를 구하는것이기에 1부터 ++ 하면서 값을 탐색했다.

 

결론은 시간초과

 

그렇다, 이 문제가 그리디로 나왔으면 Lv.2로 나오지 않을것이다.

 

그럼 탐색하는 연산을 줄여야된다.

 

두번째 시도

탐색 알고리즘 : 이진(이분) 탐색을 사용하기 

이진 탐색은 start 와 end 를 선언하고 mid 값을 이용하여 원하는 값을 탐색하는 방법이다.

이진탐색시 로직 구상도

이 그림에서는 탐색하는값 37이라는 구체적인 값이 있지만 , 

해당 문제에서는 최소 숙련도를 구하는 문제이기에 mid가 Level값으로 사용함과 동시에 매개변수가 될것이다.

 

int solution(vector<int> diffs, vector<int> times, long long limit)
{
    long long start = 1;
    long long end = limit;
    long long level = (end + start) / 2;
    long long answer; // 걸리는 시간

    do 
    {
        answer = PuzzleSolve(level, diffs, times);

        if (answer > limit )
        {
            start = level + 1;           
        }
        else
        {
            end = level - 1;
        }

        level = (end + start) / 2;
    } while (start <= end);


    return level + 1;
}

 

start = 1 , end = limit ,level = (end + start) / 2 로 초기화를 한다.

answer > limit : 해당 레벨의 소요시간이 limit 보다 큰경우 start의 값을 올린다.

answer <= limit : 해당 레벨의 소요시간이 limit 보다 작은경우 end의 값을 올린다.

이런식으로 start와 end값이 교차될때까지 진행한다.

 

나온 결과값에 +1을 해준다.

(level이 mid 값인데, 원래 이진 탐색시 mid에 low값을 더해주는것을 마지막에 해준것일뿐)

 

해당 방법을 사용하니 시간복잡도를 해결 하였다.

 

이진 탐색의 시간 복잡도는 O(logN) 이다.