lv2) 퍼즐 게임 챌린지[]

https://school.programmers.co.kr/learn/courses/30/lessons/340212

 

코드

#include <string>
#include <vector>

using namespace std;
typedef unsigned long long ll; 
int solution(vector<int> diffs, vector<int> times, long long limit) {
    ll answer = 0;
   
    ll start = 1;
    ll end = 1; // -1을 하면 타입이 unsigned이기에 언더 플로우 발생하니 아주 maximum 값으로 나오기에 주의하기
    for(int idx = 0; idx < diffs.size(); ++idx){
        if(end <diffs[idx]){
            end = diffs[idx];
        }
    }

    ll lv = (start+end)/ 2;
    // lv은 이분탐색 진행하기.
    while(start <= end){
        answer = 0;
        //실행시간 10초 제약.
        //
        for(int idx = 0; idx < diffs.size(); ++idx){
            //diffs[0] = 1이기에 첫번째 인덱스의 경우 무탈하게 diff[i] <= lv(숙련도 후보 값) 로 됨
            if(diffs[idx] <= lv){
                answer += times[idx];
            }
            else{
                ll d = diffs[idx] - lv;
                answer+= ( ((times[idx] + times[idx-1]) * d ) + times[idx] );
            }
            if(answer > limit) {
                break;
            }
        }
        if(answer > limit){
            //lv 올리기.    (예제를 보면 result보다 아래의 값은 answer 산식의 합이 limit보다 높다.)
            start = lv + 1; 
        }
        else{
            end = lv - 1; // lv 낮추기
        }
        lv = (start + end)/ 2;
    }
    
    return lv + 1;
}

풀이 설명 ( 못풀었다면 못푼이유 )

시간초과로 TC 2개 틀렸다. 프로그래머스가 10초 제한을 둔 것 같다.

이분탐색을 생각했으나, 가지치기 즉 제약조건(start, end) 개념 없이 진행했었다.

이에 TC가 모두 실패됬다.

블로그 참조하여 제약조건에 대한 힌트를 통해

문제를 해결 할 수 있었다.

---

[시간 제약 관련]

완탐 시 worst 시간 : diffs 원소의 max 값 (100,000) * diffs.size (300,000)

= 30,000,000,000

이진탐색 적용시

log2(100,000) ≈ 17번 × 300,000 = 약 510만번으로 6000배 줄일 수 있다.

---

 

첫번째 풀이 : 시간초과 ( 10초 제한)

#include <string>
#include <vector>

using namespace std;
typedef unsigned long long ll; 
int solution(vector<int> diffs, vector<int> times, long long limit) {
    ll answer = 0;
    int lv = 1;
    //r은 이분탐색 진행하기.
    for(lv; lv <= limit;++lv){
        answer = 0;
        //실행시간 10초 제약.
        //
        for(int idx = 0; idx < diffs.size(); ++idx){
            //diffs[0] = 1이기에 첫번째 인덱스의 경우 무탈하게 diff[i] <= lv(숙련도 후보 값) 로 됨
            if(diffs[idx] <= lv){
                answer += times[idx];
            }
            else{
                ll d = diffs[idx] - lv;
                answer+= ( ((times[idx] + times[idx-1]) * d ) + times[idx] );
            }
            if(answer > limit) {
                break;
            }
        }
        if(answer > limit)continue;
        return lv;
    }
    
    return lv;
}

lv는 내 숙련도를 의미하는데, 애초에 lv≤limit 자체도 비효율적이다.

퍼즐의 레벨리스트인 diffs의 원소들 중 제일 큰 값이 나의 숙련도 최대치로 제한 해두는 것이 limit 제한보다 효율적이다. 물론 답은 동일하지만 문제의 요지 및 속도면에서는 좀 더 범위를 좁히는게 좋다.