문제 링크

설명

문제가 어려워진다면 그리디가 더어려워질수도 있다라고 생각한 문제였다. 처음에는 sort를 이용하여 간단히 풀어봤지만 테스트3에서 문제가 발생하였다. return시 문자의 순서는 그대로 유지하여야 한다.

그래서 다시 0,1,2 차례로 찾아내어 뺴는 방식을 택했지만 이역시도 예외 case가 발생하였다.

결국 구글링을통해 얻어낸 결과는 앞에서부터 차례로 구간을 나눠서 max값과 maxIndex를 뽑아내면서 구간구간 찾아내는것이다. 이때 유의할점은 그 구간범위인데, max값을 하나 찾았다고 할때 그 뒤쪽은 length()-k 만큼은 유지를 계속 해야한다.

소스코드

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

using namespace std;


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

    for (int i = 0; i < number.size() - k; i++) {
        char maxNum = number[start];
        maxIndex = start;//밑의if문 안탔을경우(구간내에 max값이 없을때)
        
        for (int j = start;j<k+i;j++)
        {
            if (maxNum < number[j])
            {
                maxNum = number[j];
                maxIndex = j;
            }
        }
        start = maxIndex + 1;
        answer += maxNum;
    }


    cout << answer;
    return answer;
}
int main() {

    solution("4177252841", 4);

    return 0;
}