큰 수 만들기

---

문제

---

문제의 시간복잡도

number의 자리수는 백만개로 n의 값은 백만이다. 그렇기 때문에 $O(n)$ 이하의 풀이 방법을 사용해야 한다고 생각을 했다.

---

접근법

주어진 문자열을 k번 자를 수 있다 주어졌다.
그렇기 때문에 number의 첫번째 요소부터 k+1번째 요소까지를 확인을 하여 가장 큰 수를 가진 인덱스가 무엇인지를 알아야 한다고 생각을 했다.

만약에 k+1번째가 가장 크다면 이 때는 앞에부터 k번을 자른 것이다.
k번째가 가장 크다면 k-1번 자른 것이다.
k-1번째가 가장 크다면 k-2번 자른 것이다.

위처럼 규칙성을 찾을 수 있었다.

이 방법을 통해서 0 ~ k+1번째 요소 중에서 가장 큰 수를 첫번째에 fix를 하고 앞에 부분은 다 잘라버린다.

그리고나서 남은 자르기 가능 횟수를 저장한다.

그리고 다음 반복문을 도는데 이때는 맨 앞 요소는 제외하고 뒷 요소들만을 상대로 k+1번째의 요소까지를 비교하면서 가장 큰 값을 찾는다.

이것을 반복을 한다. k가 0이 될 때 까지

---

#include <string>
#include <vector>
#include <cmath>

using namespace std;



string solution(string number, int k) {
    string answer="";
    int max = 0;
    int max_idx = -1;
    bool check[1000000] = {false, };
    while(k != 0)
    {
        max=0;
        int cur_idx = max_idx+1;
        for(int i=cur_idx;i<=cur_idx+k;i++)
        {
            if(number[i] > max) {
                max=number[i];
                max_idx = i;
            }
        }
        
        int cnt = max_idx - cur_idx;
        
        for(int i=cur_idx;i<max_idx;i++)
        {
            check[i] = true;
        }
        
        k-=cnt;
        
        if( k > 0 && max_idx == number.size()-1)
        {
            int tmp = -1;
            while(k!=0)
            {
                check[number.size()+tmp] = true;
                tmp--;
                k--;
            }
            
            break;
        }
    }
    
    for(int i=0;i<number.size();i++)
    {
        if(check[i] == false)
            answer+=number[i];
    }
    
    return answer;
    
}

/*

연속적으로 나오는 수를 무언가를 삭제해서 가장 큰 수를 만드는 방법이 무엇인가?

큰 값이 앞에 오는게 가장 좋다. 

number에 앞쪽 k+1부분 중에서 가장 큰 인덱스를 찾는다.

그래서 그값이 k번을 모두 삭제한 경우일때면 앞에꺼 k개를 날려주면 답이고,

k-1번 삭제 할 때가 가장 크다면 1번 삭제하는 것이 남으니까

맨 앞에 하나의 인덱스 값은 고정되어 있다고 생각을 하고 number의 나머지를 본다.

한번 삭제 할때가 좋은지? 아닌지?

어떻게 구현 할 것인가?


*/

문제에서 계속 하나가 실패가 나와서 오래 걸렸다.
k가 0이 되지 않는 경우에 대해서 고려를 안했던 것이다.

예를들어 99999 라는 number가 들어와 있다면, 위의 방식으로는 k가 0이 될 수가 없다.

따라서 이 경우에는 k가 0번이 될때까지 계속 마지막 요소를 지워주는 것이 방법이 될 것이다.

---