큰 수 만들기 - 프로그래머스, c++

 

 

- 문제 풀이

"탐욕법"을 사용하는 문제였다.

 

 

- 코드

처음에 제출한 코드는 다음과 같다.

sort()함수로 정렬해 가장 큰 수부터 하나씩 뽑아 가장 큰 수를 만들었다.

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

string solution(string number, int k) {
    // 변수 선언
    string answer = "";
    vector<int> num;
    
    // string형의 number을 vector에 int형으로 넣기
    for(int i=0; i<number.size(); i++) {
        num.push_back(static_cast<int>(number[i])-48);
    }
    
    // vector num 오름 차순 정렬
    sort(num.begin(), num.end());
    
    //가장 큰 수 문자열 형태로 저장
    for(int i=num.size()-1; i>=k; i--) {
        answer += to_string(num[i]);
    }
    
    // return
    return answer;
}

 

 

하지만 이 문제에서는 주어진 문자열을 순차적으로 탐색하면서 주어진 수들의 순서를 바꾸지 않은 상태에서 가장 큰 수를 구해야 했다.

따라서 수정해 최종으로 제출한 코드는 아래와 같다.

#include <string>
#include <vector>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
 
    int numSize = number.size() - k;
    int start = 0;
    for(int i=0; i<numSize; i++) {
        char maxNum = number[start];
        int maxIdx = start;
        for(int j=start; j<=k+i; j++) {
            if(maxNum < number[j]) {
                maxNum = number[j];
                maxIdx = j;
            }
        }
        start = maxIdx + 1;
        answer += maxNum;
    }
 
    return answer;
}