[프로그래머스] 큰 수 만들기

큰 수 만들기

Algorithm: 그리디 Created: Apr 10, 2020 7:04 PM DoubleChk: No Type: 프로그래머스 link: https://programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

    #include <string>
    #include <vector>
    
    using namespace std;
    
    string solution(string number, int k) {
        string answer = "";
        int n = number.size() - k;
        
        int cur = 0;
        for(int i=0; i<n; i++){
            char max_num = number[cur];
            int max_idx = cur;
            
            for(int j = cur ; j<= k+i; j++){
                if(max_num < number[j]){
                    max_num = number[j];
                    max_idx = j;
                }
            }
            
            cur = max_idx + 1;
            answer += max_num;
            
        }
        return answer;
    }

• 문제 풀이

  dfs로 풀면 시간 초과가 난다.

  반복문을 n-k번만 돌리면 된다는 것은 다들 알 것이다.

  총 (n-k)개의 숫자 길이가 나와야 하므로

  각각의 자릿값들은 이전 인덱스 ~ (전체길이 - 나머지 남은 자릿수 길이)에서 찾으면 된다.

  예를들어,

  number = “1231234”

  k = “3”

  일때,

  number.length() - k개가 숫자의 길이다. 즉 7-3으로 4개의 숫자를 더해야 한다.

  그래서 outer loop가 0~n-k번 돌게 된다. i는 자릿수를 의미한다.

  첫 번째 큰 값은, 0부터 number.length() - 3에서 찾아야 한다.

  왜냐하면!!

  나머지 자릿수들을 찾아야 하기 때문이다. 남은 자릿수가 3개니까 최소한 3개는 남겨 놔야한다.

  inner loop는 이 작업을 한다.

  가장 큰 값과 가장 큰 값의 인덱스를 저장하고,

  innerloop가 끝나면 update를 한다.

  가장 큰 값의 다음 인덱스부터 탐색을 진행하면 된다.