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

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

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

 

 

그리디 문제는 항상 뭔가 수학적 사고를 조금 요하는듯......

 

문제를 푼 원리는 return 의 각 인덱스값을 i라고 가정했을때

 

i번 쨰 들어갈 수 있는 수는 i+k 안에서 정해야된다 입니다.

k개를 미리 버리는 카드로 가정하고 선택한 다음

범위를 늘려가기때문에 가능한 문제풀이방법입니다..

 

이걸... 생각을 해 냈는데.... 제가 푼 코드는 정말 더럽기 그지없는거같습니다..

그래서 제가푼 코드와 다른 분의 코드를 참고해서 구성한 코드 두개를 올리겠습니다

 

 

제가 푼 코드 ㅋㅋ;;

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//지저분한 버전
string solution(string number, int k) {
    string answer = "";
    int maxnum=-1;
    int j;
    for (int i = 0; i < number.size() - k; i++) {
        char max1 = '0';
        
        //i+k 까지 가장 큰 수를 찾습니다.
        for (j=maxnum+1; j <= i + k;j++ ) 
            max1 = max(max1, number[j]);            
        //가장 큰 수가 제일 먼저!! 나오는 인덱스값을 저장하고 break
        for (j = maxnum + 1; j <= i + k; j++) {
            if (max1 == number[j]) {
                maxnum = j;
                break;
            }
        }
        //답에 숫자를 추가합니다.
        answer += max1;        
    }
    return answer;
}

 

 

 

좀 더 깔끔한 버전(다른 분의 풀이를 참고했습니다)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//좀 더 깔끔한 버전
string solution(string number, int k) {
    string answer = "";
    char maxnum = '0';
    int maxidx = 0; int start = 0;
 
    for (int i = 0; i < number.size() - k; i++) {
 
        maxnum = number[start];
        maxidx = start;
        for (int j = start; j <= i + k; j++) {
            if (maxnum < number[j]) {
                maxnum = number[j];
                maxidx = j;
            }
        }
        start = maxidx + 1;
        answer += maxnum;
    }
    return answer;
}