[프로그래머스] (그리디) 큰 수 만들기 c++

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

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

 

기본적인 아이디어. 

 

구현 가능한 n-k길이의 숫자들중 가장 큰 값을 구하자

 

1. 각자리수의 가장 큰값을 가져 와서 가장 큰 수를 만든다.

2. 첫 번째 자리는 인덱스 구간 [ 0 , k ] 중 가장 큰 [i] 값을 선택.

3. 두 번째 자리는 인덱스 구간 [ i+1, k+1 ] 중 가장 큰 [i] 값을 선택.

.

.

.

4.   j 번째 자리는 인덱스 구간 [ i+1, k+(j-1) ] 중 가장 큰  [i] 값을 선택.

 

 

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

int maxfind(int num[],int st,int fi)
{
    int answer=st;
    int maxi=num[st];
    for(int i=st+1; i<=fi; i++)
    {
        if(maxi<num[i])
        {
            maxi=num[i];
            answer=i;
        }
    }
    
    return answer;
}

//https://programmers.co.kr/learn/courses/30/lessons/42883#
string solution(string number, int k) {
    string answer = "";
    int n=number.length();
    
    int num[n];
    for(int i=0; i<n; i++)
    {
         num[i]=(int)number[i]-'0' ;
    }
    
    int st=0;
    int cnt=n-k;
    
    while(1)
    {
        if(n-st==cnt)
        {
            for(int i=st; i<n; i++)
            {
                answer+=number[i];
            }
            break;
        }
        else if(cnt==0)
        {
            break;
        }
        
        st=maxfind(num,st,n-cnt);
        answer+=number[st];
       
        st++;
        cnt--;
    }
    
    return answer;
}

큰 수 만들기 실행시간