프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 C++

오늘은 이전 포스팅  2024.10.12 - [알고리즘/프로그래머스] - 프로그래머스 - [PCCP 기출문제] 1번 / 동영상 재생기 C++에 이어 2번 문제를 풀어보았다. 1번 문제보다 소요시간은 2배 정도 걸렸는데, 최초 문제 풀이는 빨랐지만 예외적인 사항을 놓쳐 테스트 14번에서 실패가 발생하였다. 다른 풀이자들의 예외적인 케이스는 나에게 문제가 되지 않았다.. 그래서 더 어려웠다... 해당 부분을 같이 공유하면서 문제를 풀이해 보자.

 

알고리즘 난이도 및 시간 ( ※ 개인적인 의견 )

• 난이도 : Level 3 ( ※ Min : 0, Max : 10 )
• 풀이 시간 : 1시간
• 제출 횟수 : 3번 ( Fail Case : 14 )
• 풀이 결과 : Pass

---

문제 설명

  문제는 나의 레벨이 어느 정도라면 제한 시간 내에 문제없이 풀 수 있는지? 에 관한 문제이다. 물론 Level이 높으면 모두 쉽게 Clear 할 수 있겠지만, 최소한 내가 이 정도 수준이라면 Clear 할 수 있는지? 에 대한 문제이다. 하지만 문제에 숨어 있는 지뢰들이 있다. 근데 문제를 풀면서 느꼈지만, 문제에 Bold로 주의해야 할 사항은 이미 다 알려줬다... 

출처 : 프로그래머스

 

 제한 사항은 크게 특별한 내용이 없기 때문에 사진만 첨부하고 넘어가겠다.

출처 : 프로그래머스

---

입출력

 - 금일은 입출력 풀이는 문제가 난도가 있음에 문제 풀이를 이해한 후에 입출력을 봐야 할 것 같아. 아래 문제 풀이를 보고 독자들이 스스로 풀어보기를 권유한다. ※ 난이도가 쉽다면... 문제 풀이 없이 바로 이해가 가능하지만 내 생각에는 알고리즘을 자주 푸는 사람이라면 쉽게 이해를 하겠지만, 이제 시작하는 독자들 입장에서는 문제 풀이가 어려울 것 같아 생략하겠다.

---

 

문제 풀이

 일단 내가 지금 퍼즐을 푸는 레벨이 나의 Level N 보다 작으면 그냥 time_cur만큼 사용하면 되고, 만약 나의 Level N보다 문제의 Level이 높다면 diff - level번을 틀리기 때문에 이전 문제까지 다시 풀어야 한다. 해당 부분을 수식으로 세운다면 아래와 같다. ※ 나는 보통 문제를 해석하면서 기능별로 함수화 하는 습관이 있다.

long long GetCurrentLevelTime(const uint32_t &rPuzzelLevel, 
                             const uint32_t &rMyLevel, 
                             const uint32_t &rPrev_Time, 
                             const uint32_t &rCurr_Time) 
{
    long long iSpendTime= 0 ;
    if( rPuzzelLevel <= rMyLevel) // 나의 레벨이 문제 레벨 보다 높은 경우
    {
        iSpendTime = rCurr_Time; 
    }
    else // 나의 레벨이 문제 레벨 보다 낮은 경우
    {
        iSpendTime = (rPrev_Time + rCurr_Time) * (rPuzzelLevel - rMyLevel) + rCurr_Time;
    }
    return iSpendTime;
}

  그다음으로 필요한 기능이 나의 적정 Level을 찾기 위한 함수가 필요하다. 나는 이진 탐색을 활용하여하였다. 여기서 중요한 점은 나의 Level은 양의 정수이기 때문에 0일 수가 없다. 또한 예외적으로 고려가 필요한 사항은 (n + m) / 2를 하였을 때 값이 n인 Case다. 이와 같은 경우는 n이 한 번 사용되었으면 m의 값을 반환할 수 있도록 고려가 필요하다. ( ※ Test Case 14번이 다음과 같은 예외적인 사항이 고려되어 있는지에 관한 문제였다... )

uint32_t GetMiddleValue ( uint32_t &rLeftValue,
                         uint32_t &rRightValue,
                         const uint32_t &rMiddleValue)
{
    uint32_t iReturnValue = 0 ;
    if( rLeftValue != rRightValue) // 서로 다르다면 같은 경우는 무조건 0을 반환하도록 설계
    {
        iReturnValue = ( rLeftValue + rRightValue ) / 2 ;
    }
    
    if( iReturnValue == rMiddleValue ) // 만약 반환하는 값이 이전 middleValue와 같다면 rightvalue를 반환하여 다음에 같은 값이 나오도록 처리
    {
        rLeftValue = rRightValue;
        iReturnValue = rRightValue;
    }
    
    return iReturnValue ;
}

 

 

 그다음 메인 함수는 while문으로 해를 구할 때까지 무한 반복을 하였고, 종료되는 조건은 GetMiddleValue가 0이 반환될 때까지 하였다. 여기서 특이한 점은 글로벌 변수로 처리하지 않고, Param으로 Min, Max 값을 조정하면서 해를 찾아갔다.

추가로 여기서 주의해야 할 점은 최소 Level을 찾아가는 과정으로 Level을 높이기는 것이 아니라 점점 낮춰가야 한다는 것이다. 

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    uint32_t vMaxDiff = *max_element(diffs.begin(), diffs.end());
    uint32_t vMinDiff = 1;
    uint32_t iMiddleValue = GetMiddleValue(vMinDiff, vMaxDiff, vMaxDiff);
    int iPrevTime = 0 ;
    answer = vMaxDiff;
    long long lTotalTime = 0;
    while( 0 != iMiddleValue ) 
    {
        lTotalTime = 0;
        iPrevTime = 0 ;
        for( uint32_t index = 0 ; index < times.size() ; ++index )
        {
            lTotalTime += GetCurrentLevelTime(diffs[index], iMiddleValue , iPrevTime, times[index] );
            iPrevTime = times[index];
        }
 
        if(lTotalTime > limit) // 리밋 보다 크면 더 작은 값을 구해야함 레벨을 높여야함
        {
            vMinDiff = iMiddleValue;
            iMiddleValue = GetMiddleValue(vMinDiff, vMaxDiff, iMiddleValue);
        }
        else if(lTotalTime < limit) // 리밋 보다 작으면 더 큰 값을 구해야함 
        {
            if( answer > iMiddleValue )
            {
                answer = iMiddleValue ;
            }
            vMaxDiff = iMiddleValue;
            iMiddleValue = GetMiddleValue(vMinDiff, vMaxDiff, iMiddleValue);
        }
        else // 같으면 Stop
        {
            if( answer > iMiddleValue )
            {
                answer = iMiddleValue ;
            }
            break;
        }
    }
    
    return answer;
}

---

결과

 혹시나, 문제 풀이를 보고 이해가 가지 않는 내용이 있다면 댓글로 남겨주면 답변할 수 있도록 하겠다. 바보 같이... 예외적인 케이스를 고려하지 못해 1번 틀린 점에 관해서는 문제를 조금 더 디테일하게 읽고, 예외적인 케이스를 조금 더 설계했다면 좋았을 것 같다.

출처 : 프로그래머스

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=cpp#

프로그래머스