프로그래머스 - [PCCP 기출문제] 4번 / 수식 복원하기 C++

 오늘은 PCCP 마지막 문제 4번 포스팅을 하려고 한다. 2024.10.14 - [알고리즘/프로그래머스] - 프로그래머스 - [PCCP 기출문제] 3번 / 충돌위험 찾기 C++ 문제란 난이도 자체는 내가 느끼기에 비슷하다고 느꼈다. 다만 코드의 양이 조금 더 많은? 느낌이었고, 구현의 양으로 인해 검증도 한다고 3번 문제보다 시간은 조금 더 소요되었다. 같이 한 번 문제를 해석해 보자.

 

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

• 난이도 : Level 4 ( ※ Min : 0, Max : 10 )
• 풀이 시간 : 2시간
• 제출 횟수 : 2번 ( 예외 처리 실수 )
• 풀이 결과 : Pass

---

문제 설명

 이번 문제 해석은 2번 3번보다 간결하고 이해하기도 쉽다. 그냥 전달받은 수식이 어떤 진법으로 해결해야 하는지 찾은 후 답을 찾는 문제이며, 여러 진법이 겹쳐서 가능한 경우에는?로 알 수 없음으로 표현하면 끝이다. 하지만 만약 N진법에 대해서 지식이 없다면 풀기에 어려움이 있다. 해당 포스팅에서는 N진법에 대해서 다 안다는 가정하에 문제풀이를 진행하겠다.

출처 : 프로그래머스

  제한 사항에서 얻을 수 있는 정보는 아래와 같다.

• A, B는 음이 아닌 두 자릿수 이하의 정수
• C는 X 혹은 음이 아닌 세 자릿수 이하의 정수
• 결괏값이 음수가 되거나 서로 모순되는 수식은 X

출처 : 프로그래머스

---

문제풀이

 이번 문제를 해석하면서 필요하다고 생각된 기능들은 다음과 같다.

• 수식으로부터 값을 추출하는 함수 : X인 경우에는 result 값이 중요하지 않기 때문에 고려하지 않았다.

//==============================================
// @ 수식으로 부터 값을 추출하는 함수
void GetExpressionValue(const string& rExpression,
    uint8_t& rLeftValue,
    uint8_t& rRightValue,
    uint16_t& rResult,
    bool & isAdd)
//==============================================
{
    stringstream ss(rExpression);
    string leftValue = "";
    string sign = "";
    string rightValue = "";
    string equal = "";
    string resultValue = "";
    ss >> leftValue >> sign >> rightValue >> equal >> resultValue;
    rLeftValue = stoi(leftValue);
    rRightValue = stoi(rightValue);
    if ("X" != resultValue)
    {
        rResult = stoi(resultValue);
    }
    if ("+" == sign)
    {
        isAdd = true;
    }
    else
    {
        isAdd = false;
    }
}

• 10진수를 N Sacle(진법) 값으로 반환 : 문제를 풀면서 10진법으로 바꿔서 result를 구해야지 하면 안 된다. result는 N진법으로 계산한 값이기 때문에 필요하다고 판단하여 구현하였다. 여기서 주의사항은 result가 3자리 이하라고 하였기 때문에 단순 하드코딩으로 구현하였다.

//==============================================
// @ 10진수를 N Sacle값으로 반환
uint16_t ConvertTenToNScale( const uint8_t& rScale,
                             const uint16_t& rResult )
//==============================================
{
    uint16_t iResult = 0;
    uint16_t tempResult = rResult;
    uint16_t tempValue = tempResult / (rScale * rScale);
    tempResult -= (tempValue * (rScale * rScale));
    iResult = tempValue * 100;
    tempValue = tempResult / rScale;

    tempResult -= (tempValue * rScale);
    iResult += tempValue * 10;

    iResult += tempResult;

    return iResult;
}

• 수식의 결과값을 반환하는 함수 : 추출한 숫자를 기반으로 result 값을 계산하는 함수를 만들었다. 범용성을 위해 특정 진법이 아닌 N 진법에 맞는 수식이 나오도록 구현하였다. 여기서 isAdd는 +를 해야 할지 -를 해야 할지 고려가 필요하기 때문에 필요하다. 만약 음수가 나올 수 있다면 머리가 아팠을 텐데 해당 문제는 모두 양수라 간단했다.

//==============================================
// @ 수식의 결과값을 반환하는 함수
uint16_t GetResult(const uint8_t& rScale, // n진법
    const uint8_t& rLeftValue, // 수식 왼쪽 값
    const uint8_t& rRightValue,
    const bool& isAdd) // 수식 오른쪽 값
//==============================================
{
    uint8_t iLeftFirst = rLeftValue / 10;
    uint8_t iLeftSecond = rLeftValue % 10;

    uint8_t iRightFirst = rRightValue / 10;
    uint8_t iRightSecond = rRightValue % 10;

    uint16_t iResult = 0;
    uint16_t tempResult = 0;
    if (true == isAdd)
    {
        tempResult = ((iLeftFirst * rScale) + iLeftSecond) + ((iRightFirst * rScale) + iRightSecond);
    }
    else
    {
        tempResult = ((iLeftFirst * rScale) + iLeftSecond) - ((iRightFirst * rScale) + iRightSecond);
    }
    iResult = ConvertTenToNScale(rScale, tempResult);
    return iResult;
}

 

• 최소한 N Scale(진법)을 반환하는 함수 : 수식을 보면 최소한의 N진법이 된다는 힌트를 얻을 수 있다. 예를 들어 7이라는 값이 들어 있다면 2~7진법은 고려대상이 아니라는 것이다. 

//==============================================
// @ 최소한의 진법이 얼마인지 구하는 함수
uint8_t GetMinimumScale(const uint8_t& rLeftValue, // 수식 왼쪽 값
                        const uint8_t& rRightValue)
//==============================================
{
    uint8_t iMinScale = 1;
    uint8_t iLeftFirst = rLeftValue / 10;
    uint8_t iLeftSecond = rLeftValue % 10;

    uint8_t iRightFirst = rRightValue / 10;
    uint8_t iRightSecond = rRightValue % 10;

    if (iLeftFirst >= iMinScale)
    {
        iMinScale = iLeftFirst;
    }
    if (iLeftSecond >= iMinScale)
    {
        iMinScale = iLeftSecond;
    }
    if (iRightFirst >= iMinScale)
    {
        iMinScale = iRightFirst;
    }
    if (iRightSecond >= iMinScale)
    {
        iMinScale = iRightSecond;
    }
    iMinScale += 1;
    return iMinScale;
}

• n진법이 가능한지 확인하기 위한 함수 : 전달 받은 N진법으로 계산 시 식이 성립되는지 확인하는 함수다.

//==============================================
// @ n진법이 가능한지 확인하기 위한 함수
bool IsPossible(const uint8_t& rScale, // n진법
    const uint8_t& rLeftValue, // 수식 왼쪽 값
    const uint8_t& rRightValue, // 수식 오른쪽 값
    const uint16_t& rResult,
    const bool &isAdd) // 결과 값
//==============================================
{
    bool bIsPossible = false;

    uint16_t iAddValue = GetResult(rScale, rLeftValue, rRightValue, isAdd);

    if (rResult == iAddValue)
    {
        bIsPossible = true;
    }

    return bIsPossible;
}

• 유효한 수식을 활용하여 가능한 Scale을 반환하는 함수 : 유효한 수식중에서 가능한 Scale 후보군이 무엇인지 추출하는 함수다.

//==============================================
// @ 유효한 수식을 활용하여 가능한 Scale을 반환하는 함수
vector<uint8_t> GetPossibleScale(const vector<string>& expressions)
//==============================================
{
    vector<uint8_t> vCanScale = { true, true, true, true, true , true, true, true }; // 2~9 모두 가능하다고 true 처리
    uint8_t iExpressionSize = static_cast<uint8_t>(expressions.size());
    bool isAdd = false;
    uint8_t iLeftValue = 0, iRightValue = 0;
    uint16_t iResult = 0;
    for (uint8_t index = 0; index < iExpressionSize; ++index)
    {
        for (uint8_t scaleIndex = 0; scaleIndex < MAX_SACLE_COUNT; ++scaleIndex)
        {
            if (true == vCanScale[scaleIndex])
            {
                iLeftValue = 0;
                iRightValue = 0;
                iResult = 0;
                isAdd = false;
                GetExpressionValue(expressions[index], iLeftValue, iRightValue, iResult, isAdd);
                if (false == IsPossible((scaleIndex + 2), iLeftValue, iRightValue, iResult, isAdd))
                {
                    vCanScale[scaleIndex] = false;
                }
            }
        }
    }
    return vCanScale;
}

 

• 수식을 전달 받아 추측이 가능한 수식과 불가능한 수식을 나누는 함수 : 처음에 받은 수식을 구분하여 진행했다. 한 번에 하면 순서적으로 볼 때 복잡할 것 같아 구분하기 위해 만들었다.

//==============================================
// @ 수식을 전달 받아 추측이 가능한 수식과 불가능한 수식을 나누는 함수
void SeperateExpression(const vector<string>& rExpressions,
    vector<string>& rCanExpect,
    vector<string>& rCantExpect)
//==============================================
{
    uint8_t iExpressionSize = static_cast<uint8_t>(rExpressions.size());
    for (uint8_t index = 0; index < iExpressionSize; ++index)
    {
        uint8_t iSLength = rExpressions[index].length();
        if ('X' == rExpressions[index][iSLength - 1])
        {
            rCantExpect.push_back(rExpressions[index]);
        }
        else
        {
            rCanExpect.push_back(rExpressions[index]);
        }
    }
}

• 결괏값을 반환하는 함수 : 실제로 정답을 구하는 함수이며, 추출된 가능한 Scale 및 실제로 정답에 활용되는 수식은 " = X" 수식이기 때문에 인자로 해당 부분은 받는다.

//==============================================
// @ 결과값을 반환하는 함수
void GetAnswer(const vector<uint8_t>& rPossibleScale,
    const vector<string>& rCantExpect,
    vector<string>& rAnswer)
//==============================================
{
    uint8_t iScaleSize = static_cast<uint8_t>(rPossibleScale.size());
    uint8_t iExpressionSize = static_cast<uint8_t>(rCantExpect.size());
    bool isAdd = false;
    uint8_t iLeftValue = 0, iRightValue = 0;
    uint16_t iResult = 0, iPrevResult = MAX_RESULT_VALUE;
    string sTemp;
    for (uint8_t exIndex = 0; exIndex < iExpressionSize; ++exIndex)
    {
        sTemp = rCantExpect[exIndex];
        iPrevResult = MAX_RESULT_VALUE;
        for (uint8_t scIndex = 0; scIndex < iScaleSize; ++scIndex)
        {
            if (true == rPossibleScale[scIndex])
            {
                iLeftValue = 0;
                iRightValue = 0;
                iResult = 0;
                isAdd = false;
                GetExpressionValue(rCantExpect[exIndex], iLeftValue, iRightValue, iResult, isAdd);
                iResult = GetResult((scIndex + 2), iLeftValue, iRightValue, isAdd);
                if (MAX_RESULT_VALUE != iPrevResult)
                {
                    if (iPrevResult != iResult)
                    {
                        break;
                    }
                }
                iPrevResult = iResult;
            }
        }

        sTemp.pop_back();
        if (iPrevResult != iResult)
        {
            sTemp += '?';
        }
        else
        {
            sTemp += to_string(iResult);
        }
        rAnswer.push_back(sTemp);
    }
}

• 가능한 Scale을 미완성된 수식을 보고 업데이트하는 함수 :GetMinimumScale를 활용하여 유효한 수식에서 추출된 진법 후보군을 한 번 더 필터링하는 컨트롤 함수다.

//==============================================
// @가능한 Scale을 미완성된 수식을 보고 업데이트 하는 함수
void UpdateSacle(vector<uint8_t>& rPossibleScale, 
                 const vector<string>& rCantExpect )
//==============================================
{
    uint8_t iExpressionSize = static_cast<uint8_t>(rCantExpect.size());
    for (uint8_t exIndex = 0; exIndex < iExpressionSize; ++exIndex)
    {
        bool isAdd = false;
        uint8_t iLeftValue = 0, iRightValue = 0;
        uint16_t iResult = 0;
        GetExpressionValue(rCantExpect[exIndex], iLeftValue, iRightValue, iResult, isAdd);
        uint8_t minimunScale = GetMinimumScale(iLeftValue, iRightValue);
        for (uint8_t scIndex = 0; scIndex < minimunScale - 2; ++scIndex)
        {
            if (true == rPossibleScale[scIndex])
            {
                rPossibleScale[scIndex] = false;
            }
        }
    }
}

• 메인 함수 :위에 기재된 함수들을 활용하여 문제를 도출하기 위해 컨트롤 하는 함수다. 

//==============================================
vector<string> solution(vector<string> expressions) {
//==============================================
    vector<string> answer; // 정답
    vector<string> vCanExpect; // 정답이 기재되어 있는 수식
    vector<string> vCantExpect; // 정답이 기재되어 있지 않은 수식
    SeperateExpression(expressions, vCanExpect, vCantExpect); // 정답 기재 유무에 따른 분리
    vector<uint8_t> vPossibleScale = GetPossibleScale(vCanExpect); // 가능한 진법 가져오기
    UpdateSacle(vPossibleScale, vCantExpect);// 불가능한 수식들 보고 한 번 Update를 모두 진행해야함 
    GetAnswer(vPossibleScale, vCantExpect, answer); // 정답 가져오기
    return answer;
}

---

결과

 처음에 TestCase 1번 2번을 틀렸는데, 무엇이 문제일까 코드 리뷰를 하던 중 GetMinimumScale의 Default 값이 2로 기재하여 2진법 케이스를 거르지 못해 생기는 문제였다. 해당 부분을 해결 후 아래와 같이 통과하였다. 개인적인 생각에는 2번 3번보다 훨씬 더 쉬운 문제로 느껴졌다. 다만 개인적인 Level을 높인 이유는 코드의 양과 문제 해석보다는 논리적인 사고가 더 중요하다고 생각되어 Level4로 분류하였다.

출처 : 프로그래머스

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/340210

프로그래머스