프로그래머스 큰 수 만들기 c++,java (탐욕법)

문제 출처 : 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의 자릿수미만인 자연수입니다.

입출력 예

출처

풀이

'프로그래머스 / 탐욕법(Greedy) / 큰 수 만들기'로 분류되어 있는 문제이다.

예제 테스트케이스는 통과했는데, 효율성이랑 추가 테스트케이스에서 불통으로

몇 시간 고민하다가 결국 다른 사람의 풀이를 봤다.

 

우선 number= "4177252841", k =4일 때,

4개의 수를 빼야 하므로 6자리 숫자를 만들어야 하고,

주어진 number의 순서를 뒤집을 순 없고, 차례대로 수들을 조합해서 가장 큰 수를 만들어야 한다.

 

앞에서부터 큰 수를 찾아야 하고, 큰 수를 제외한 나머지를 버린다고 했을 때, 최소 6자리의 숫자는 만들 수 있어야 한다.

4 1 7 7 2 중에 큰 수를 찾고, 7을 제외한 나머지 4 1 7 2를 버려도 뒤의 5 2 8 4 1을 붙이면 6자리 숫자를 만들 수 있다.

가장 큰 수 7을 찾았으면, answer의 첫 번째 자릿수를 찾은 것이고,

두 번째, 세 번째 네 번째 반복하여 여섯 번째 자릿수까지 찾으면 된다.

 

4 1 7 7 2를 탐색하면

number[2]의 7이 가장 큰 수이고

answer = 7이다.

 

이후, number[3]인 7부터 7 2 5를 탐색하면 ( 7을 제외한 2,5를 버려도 나머지 2 8 4 1로 6자리 answer 완성 가능)

number[3]의 7이 가장 큰 수이고

answer = 77이다.

 

number[4]인 2부터 2 5 2를 탐색하면 (5를 제외한 2,2를 버려도 나머지 8 4 1로 6자리 answer 완성 가능)

number[5]의 5가 가장 큰 수이고,

answer = 775이다.

 

number[6]인 2부터 2 8을 탐색하면 (8을 제외한 2를 버려도 나머지 4 1로 6자리 answer 완성 가능)

number[7]의 8이 가장 큰 수이고,

answer = 7758이다.

 

number[8]인 4부터 4를 탐색하면

number[8]의 8이 가장 큰 수이고,

answer = 77584이다.

 

number[9]인 1부터 1을 탐색하면

number[9]의 1이 가장 큰 수이고,

answer =775841이다.

코드1(c++)

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";

    int n= number.length()-k;

    for(int i=0,idx=-1; i<n;i++){
        char max='0';
        for(int j=idx+1;j<=k+i;j++){
            if(max<number[j]){
                max = number[j];
                idx=j;
            }
        }
        answer+=max;
    }


    return answer;
}

코드2(java)

import java.util.Arrays;
class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();

        for(int i=0, idx =-1; i<number.length()-k;i++){
            int max=0;
            for(int j=idx+1; j<=k+i;j++){
                if(max<number.charAt(j)-'0'){
                    max = number.charAt(j)-'0';
                    idx = j;
                }
            }
            answer.append(max);
        }
        return answer.toString();
    }
}