[프로그래머스 고득점 kit] 큰 수 만들기 c++ (greedy)

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=cpp 

프로그래머스

 

 

문제 풀이

해당 문제는 최대 1000000 자리 수 이므로, 모든 가능성을 Combination 구현을 통해 탐색하는 '완전 탐색' 알고리즘을 통해 최대 값을 찾을 시, 시간 초과가 발생한다. 

여기서, 1가지 규칙을 찾아 greedy로 문제를 해결할 수 있다.

바로 대소 비교의 특성이다.

9111>8999 
아무리 다른 자리의 숫자가 커도, 맨 앞자리가 큰 것이 무조건으로 크다.
따라서, 앞에서 부터 '최대한 큰 수' 를 선택하면서 나아가면 된다.

 

문제에선 무조건 k개의 수를 제거하라고 했으므로, 앞에서 부터 가능한 가장 큰 수를 선택해나가는 과정을  N-k번 반복하여, 모든 수를 선택하면 된다. 

 

greedy는 이와 같이, 순서 등을 기준으로, 현재의 최대 or 최소가 전체의 최소, 최대를 구하는 과정으로 이어지는 부분을 찾는 것이 핵심이다. ( 이경우, 가장 앞자리 부터  최대 값이 되도록 찾아나가면,  전체의 최대 값을 찾을 수 있다. )

 

 

정답 코드

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

string solution(string number, int k) {
    string answer = "";
    //i째 자리수에 올 수 있는 숫자 중 가장 큰 수의 인덱스 값 저장.
    int idx=-1;
    int len=number.size();
    //i번째 자리 수 선택하기
    for(int i=0;i<len-k;i++){
        int mx=-1;
        //앞으로 선택해야할 수의 개수
        int left_choose=(len-k)-i; 
        for(int j=idx+1;j<len;j++){
            //idx번째 수 선택시, 앞으로 고를 수 있는 수의 개수
             int  left_num= len-j;
            if(  left_choose> left_num ) break; //해당 idx 이후의 수는 선택 불가
            if(mx<number[j]){//선택 가능한 수 중, 최대값 선택
                mx=number[j];
                idx=j;
            }
        }
        answer+=number[idx];
        len++;
        if(number.size()-k==len) break;
    }
    return answer;
}

주의

12390 라는 숫자의 모음에서, 1개를 제거해야한다고 가정하자.

위에서, 가장 큰 수는 '9' 이다. 하지만 9 이후엔 1개의 숫자밖에 존재하지 않는다. 

우리는 총 5-1=4개의 숫자를 선택해야하는데, '9'는 가장 큰 수  이지만, 가장 앞자리에 올 수 없다.

따라서 '가장 큰 수'를 선택해나가는 과정에서, 해당 수가 지정된 자리 수에 위치할 수 있는지 조건을 체크하며 구해야한다.

 

 

 

시간 초과 코드

아래는 combination을 통해, 전체 N개의 수 중, k개의 수를 제거 했을 때, 해당 숫자열의 값을 모두 구한 뒤, 그 중 최대 값을 찾는 '완전 탐색'을 통한 풀이법이다. 시간 초과가 났기에 배제하였다.

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

int del[1000000];
int kk,len;
string mx="0";
string num;
void comb(int depth,int select){

    if(depth==len){
        if(select<kk)return;
        string ans="";
        for(int i=0;i<len;i++){
            if(del[i]==1)continue;
            ans+=num[i];
        }
        if(mx.compare(ans)<0)mx=ans;
        return;
    }
    comb(depth+1,select);// 해당 num 제거 x
     if(select==kk) return; //이미 제한된 수 제거 끝
    del[depth]=1;
    comb(depth+1,select+1); //해당 num 제거 후
    del[depth]=0;
}



string solution(string number, int k) {
    string answer="";
    num=number;
    kk=k;
    len=number.size();
    comb(0,0);
    answer=mx;
    return answer;
}