[C++] level2 큰 수 만들기 42883

📌큰 수 만들기

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

문제를 보면 숫자에서 두 수를 제거해서 만든다고 명시되어 있는데 앞에서부터만 지울 수 있다는 건 명시되어 있지않다 ...
하지만 입출력 예시를 보면 앞에서부터 작은 수를 제거한다..... 주의하자 !

먼저 문자 수가 4자리인데 k만큼 뺀 수를 제거하면 2자리만 출력하면 된다.
그래서 for문은 number.size() - 2 한 값 만큼 돌려주었다.
그리고 for문 안에서 가장 큰 value 값을 구해서 idx 갱신하며 가장 큰 값들만 answer에 더해주었다.
이 풀이의 주의점은 for문 내 for문에서 첫번째 인덱스부터 검사해주기 위해 idx를 초기에 -1로 설정한 점이다!

📌코드

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

string solution(string number, int k)
{
    string answer = "";

    //k만큼 뺀 수만 출력
    int idx = -1; //0번째 인덱스부터 검사하기 위함
    for (int i = 0; i < number.size() - k; i++)
    {
        char maxValue = ' ';
        for (int j = idx + 1; j <= k + i; j++)
        {
            if (maxValue < number[j])
            {
                maxValue = number[j]; //갱신
                idx = j;
            }
        }
        answer += maxValue;
    }
    return answer;
}

---

회고
greedy 하게 문제를 푸는 건 생각보다 어렵다.
이론 상으로 이해하는건 어렵지 않은데 문제를 greedy하게 접근하는 것은 어려운 것 같다.