(프로그래머스 c++)큰 수 만들기

탐욕법을 이용한 알고리즘 문제이다..!

 

우선 limit 변수를 선언하여 number.size() - k 를 대입하였다.

while문을 통해 구하고자 하는 큰 수의 size 를 구하기 위함이다..!

 

그리고 answer.size()가 limit이 될 때 까지 반복하도록 한다.

1) 반복자를 선언하여 number.begin()으로 위치시킨다.

2) k가 1이 아니면 number.begin()부터 k + 1 까지의 수 중 최댓값의 위치를 찾고,

   k가 1인 경우 number.begin()부터 2 까지의 수 중 최댓값의 위치를 찾아 itr에 넣어준다.

(k가 1인 경우는 2개의 숫자만 비교하는 이유는 최악의 경우를 생각해야 하기 때문..!)

3) answer에 최댓값을 넣어주고, number에서는 begin()부터 최댓값을 포함한 위치까지 erase 해준다.

4) 만약 itr이 number.begin()이 아닌 경우 k -= itr - number.begin()을 해준다.

(3번에서 최댓값을 포함한 위치까지 지웠지만, k는 최댓값 이전의 개수를 빼줘야 하기 때문..!)

   하지만 itr이 number.begin()이라면 최댓값의 위치가 number의 맨 앞이기 때문에 k에서 수를 뺄 필요가 없다..!

 

이렇게 하면 무리 없이 문제를 풀 수 있다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int limit = number.size() - k;
    while(answer.size() != limit)
    {
        auto itr = number.begin();
        if(k != 1)
            itr = max_element(number.begin(), number.begin() + k + 1);
        else if(k == 1)
            itr = max_element(number.begin(), number.begin() + 2);
        answer.push_back(*itr);
        number.erase(number.begin(), itr + 1);
        if(itr != number.begin())
            k -= itr - number.begin();
    }
    return answer;
}