C++:: 프로그래머스 < 큰 수 만들기 >

시간초과 때문에 애를 먹은 문제이다. 풀이의 핵심은 가장 범위 내의 가장 큰수를 추가해주고 인덱스를 해당 인덱스로 고정해 구간을 설정해 준다는 점이다.

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

string solution(string number, int k) {
    string answer = "";
    int idx = -1;
    for(int i=0; i<number.size()-k; i++) {// 길이가 k+1 인 구간으로 쪼개어서 본다 생각하면 된다.
        string::iterator iter = max_element(number.begin() + idx + 1, number.begin() + k + 1 + i);
        idx = iter - number.begin();// 가장 큰수의 인덱스 저장
        answer += *iter;// 가장 큰수 더해준다.
    }
	return answer;
}

과정을 보면 좀더 이해하기 쉽다.

/*number_size = 10, k = 4
i는 시작 인덱스, *은 범위내 가장 큰수
범위내 가장큰수인덱스 + 1은 다음 범위에서 시작인덱스가 된다.
[41772]  52841
 i
   *
4 [17725] 2841
    i
     *
41 [77252] 841
     i
       *
417 [72528] 41
       i
         *
4177 [25284] 1
         i
          *
41772  [52841]
           i
            *
*/