[프로그래머스][C++] 큰 수 만들기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

풀이

💡 문제 접근

• k개의 수를 제거 = ( number.length() - k )개의 수를 뽑는 것
• 가장 큰 수를 뽑는다.
• 앞 자리가 클 수록 크다.

1. 0번째 인덱스부터 k번째까지의 범위 내에서 가장 큰 수를 찾는다.
2. 뽑은 수 (가장 큰 수)를 answer에 삽입하고 그 수의 인덱스를 저장한다.
3. 뽑은 수의 인덱스 다음 인덱스부터 다시 가장 큰 수를 찾는다. 이때, 탐색 범위를 1 늘려준다. (k + i 활용)

 

(ex) number = "4177252841" / k = 4 / answer의 자릿수 = 10 - 4 = 6자리

1. 0 ~ 4번째 "41772" 에서 가장 큰 수 = 7 / idx = 2/ answer = "7"
2. 3 ~ 5번째 "725" 에서 가장 큰 수 = 7  / idx = 3 / answer = "77"
3. 4 ~ 6번째 "252" 에서 가장 큰 수 = 5  / idx = 5 / answer = "775"
4. 6 ~ 7번째 "28" 에서 가장 큰 수 = 8  / idx = 7 / answer = "7758"
5. 8 ~ 8번째 "4" 에서 가장 큰 수 = 4 / idx = 8 /  answer = "77584"
6. 9 ~ 9번째 "1" 에서 가장 큰 수 = 1 / idx = 9 /  answer = "775841"

코드

#include <iostream>
#include <vector>

using namespace std;

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

    // number.length() - k 수 뽑기
    for (int i = 0; i < number.length() - k; i++) {
        char max_num = '0';
        for (int j = idx + 1; j <= k + i; j++) {    // 가장 큰 수 찾기
            if (max_num < number[j]) {
                max_num = number[j];
                idx = j;
            }
        }
        answer += max_num;
    }

    return answer;
}