[Algorithm] Programmers :: 큰 수 만들기

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

코딩테스트 연습 - 큰 수 만들기

int maxNum(string& number, int& startIndex, int destIndex)
{
    int maxNum = -100;
 
    for (int i = startIndex; i <= destIndex; i++)
    {
        if (maxNum < number[i] - '0')
        {
            startIndex = i;
            maxNum = number[i] - '0';
        }
    }
 
    return maxNum;
}
 
 
string solution(string number, int k) {
    string answer = "";
 
    int spareNum = number.size() - k; // 남은 여분의 글자개수
    int startIndex = 0;
    int destIndex = number.size() - spareNum; // 2
 
    while (answer.size() != number.size() - k)
    {
        if (startIndex >= number.size() - 2) // 끝에서 두번째랑 첫번째꺼.
        {
            if (spareNum == 2)
            {
                answer += number[number.size() - 2];
                answer += number[number.size() - 1];
                return answer;
            }
            else if(spareNum == 1)
            {
                int last2 = number[number.size() - 2] - '0';
                int last1 = number[number.size() - 1] - '0';
 
                answer += to_string(max(last2, last1));
                return answer;
            }
        }
        else
        {
            answer += to_string(maxNum(number, startIndex, destIndex));
            startIndex += 1;
            destIndex += 1;
            spareNum--;
        }
    }
 
    return answer;
}

 

나름 문제보자마자 생각나는대로 구현해본건데 제대로 작동한다.

메인로직은 else문이고, 위에 if문(startIndex >= numbers.size() -2)의 안에있는 if문,else if문은 사실 약간의 하드코딩이다.. 반복문을 진행하다보면 마지막 두개에서 spareNum이 1이거나 2라서 일단 구현하고 되는지부터 체크하기위해서 저렇게 제출했다. spareNum은 +해야하는 남은 글자개수인데, 만약 spareNum이 2개면 체크할 number의 원소도 끝에서 두개밖에 안남았기 때문에 그거 그대로 answer에 더해주면된다.

spareNum이 1인데(answer에 추가할 남은 글자개수) number의 원소가 끝에서 두개 남았다면, 그냥 둘 중 큰수를 answer에 더해주면 된다.

 

다른사람의 풀이를보면 간단하게 다듬은 코드가 있다. 개인적으로 제일 정석적이고 모범적인 답안같다.

큰 틀은 같다. 기본적으로 많이 어려운 문제가 아니라서 대부분 틀은 많이 비슷비슷한것같다.

개인적으로 그리디문제는 내 취향에 잘 안맞는다..

string solution(string number, int k) {
    
    string answer = "";
 
    int maxIndex = 0;
    int maxNum = -1;
 
    for (int i = 0; i < number.size(); i++)
    {
        if (number[i] - '0' > maxNum)
        {
            maxNum = number[i] - '0';
            maxIndex = i; 
        }                
 
        if (i == k)
        {
            answer += to_string(maxNum);
            i = maxIndex;
            k++;
            maxNum = 0;
        }
    }
 
    return answer;
}