Level 2. 큰 수 만들기

Level 2. 큰 수 만들기

 

 

이미 k개만큼 제거했는데 뒤 숫자가 남았거나, answer가 비어있으면 삽입한다.

 

answer의 마지막 수보다 작은 수면 삽입하고, 큰 수면 그 수보다 크거나 같은 수가 나올 때까지 1개씩 제거하면서 answer에서 다시 뺀 후 삽입한다.

 

솔직히 미리 알고리즘을 생각하고 풀었다기보다는 그냥 조건에 맞춰 그때그때 추가하면서 풀었다.

 

#include <iostream>

using namespace std;

string solution(string number, int k)
{
    size_t len = number.length();
    string answer;

    for (int i = 0; i < len; ++i)
    {
        if (k == 0 || answer.empty() || answer.back() >= number[i])
        {
            if (i + k < len)
                answer.push_back(number[i]);
        }
        else
        {
            while (0 < k && !answer.empty() && answer.back() < number[i])
            {
                answer.pop_back();
                --k;
            }

            answer.push_back(number[i]);
        }
    }

    return answer;
}

 

다른 사람의 풀이다.

 

i가 k번째가 됐을 때(지금까지 훓어본 수 중에 하나를 선택해야 할 때), 이전 최댓값 이후부터 k번째 수 중 최댓값을 선택하는 방식이다.

 

그러면 앞에서부터 k번째까지의 수 중 최댓값을 선택해야 할 때 항상 가장 큰 수를 가져올 수 있게 된다.

 

#include <iostream>

using namespace std;

string solution(string number, int k)
{
    string answer;
    size_t len = number.length();
    char max = '\0';
    int maxIdx = 0;

    for (int i = 0; i < len; ++i)
    {
        if (max < number[i])
        {
            max = number[i];
            maxIdx = i;
        }

        if (i == k)
        {
            ++k;
            answer.push_back(max);

            i = maxIdx;
            max = '\0';
        }
    }

    return answer;
}