[프로그래머스] Level2 - 큰 수 만들기(C++)

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

코딩테스트 연습 - 큰 수 만들기

[풀이] Greedy

 

Upperbound를 이용해서 고를 수 있는 범위 내에서 9~0까지 for문을 돌면서 가장 먼저 선택할 수 있는

값을 하나씩 고르면 된다.

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    vector<int> a[10];
    for (int j = 0; j < number.size(); j++) {
        a[number[j] - '0'].push_back(j);
    }
    
    int cur = -1;
    for (int i = k; i < number.size(); i++) {
        for (int j = 9; j >= 0; j--) {
            if (a[j].empty()) continue;
            if (answer == "" && j == 0) continue;
            auto ub = upper_bound(a[j].begin(), a[j].end(), cur);
            if (ub == a[j].end()) continue;
 
            int m = ub - a[j].begin();
            if (a[j][m] <= i) {
                answer.push_back(j + '0');
                cur = a[j][m];
                break;
            }
        }
    }
    return answer;
}

 

https://github.com/has2/Algorithm/blob/master/programmers/level2/%ED%81%B0%20%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp