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

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

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

 

후기

진짜 뇌가 다 굳은거 같다. 이해가 안되서 다른분들 블로그 3개 진짜 정독한듯

 

풀이

1. 숫자의 길이가 n일때 k개를 짤라버리는 거니까 최종 출력의 길이는 n-k다.

-> 앞에 K개를 다 짤라먹을 생각을 하고 0부터 시작해서 K+1 개씩 계속해서 젤 큰 수를 찾는거다.

-> 총 선택해야할 숫자의 갯수는 n-k

 

ex)

1) 0~k+1 중에 가장 큰 숫자 택 1

중간에 가장 큰 숫자의 index가 3이였다고 치면

2) 4~K+2 까지 중에 큰 숫자 택 1

 

-> 만약 k+1번이 젤 큰 숫자였다해도 상관없다.

3) 이렇게 되면 이 직후 k+2~k+2중 선택이니 계속 K+2가 선택 될 것이다. - 반복

 

 

 

 

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    vector<int> num;
    
    for(int i=0;i<number.size();i++)
    {
        num.push_back(number[i]-'0');
    }
    
    int start_index =0;
    
    for(int i=0;i<num.size()-k;i++)
    {
        int max_num = num[start_index];
        int index = start_index;
        for(int j=start_index;j<=i+k;j++)
        {
            if(num[j]>max_num)
            {
                max_num = num[j];
                index =j;
            }
        }
        start_index = index+1;
        answer += to_string(max_num);
    }
    
    return answer;
}