프로그래머스 큰 수 만들기 c언어 - peulogeulaemeoseu keun su mandeulgi ceon-eo

문제 설명

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

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

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

제한 조건

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

입출력 예

구현

앞서 탐욕법에 대하여 정리해놓은 것처럼 탐욕법은 현재 볼 수 있는 대상 중에서 조건에 만족하는 가장 좋은 경우의 수를 찾는 문제이다.

해당 문제에 대한 해결법은 다음과 같다. 첫 번째 예에서 우리는 1924에서 2개의 수를 뽑아야 한다. 문제 설명에서 주어진 예시처럼 조합을 통하여 모든 경우의 수를 만들어내고 그중에서 가장 큰 수를 뽑아낼 수도 있다.

하지만 그런 식으로 문제를 푼다면 우리는 1924의 순서가 변하지 않는 상황에서 2개의 수로 만들 수 있는 가장 큰 수를 뽑아내야 하는데 그것을 코딩으로 옮기기가 과연 쉬울까? 하는 생각을 해보아야 한다.

그렇다면 접근 방법을 바꾸어 가장 앞에서부터 수를 보는 것이다.

1924에서 2개를 골라서 가장 큰 수를 뽑는 방법은 다음과 같다. (뽑아낼 개수 j = n-k)

1. j = 2이고 2 자릿수를 만들어야 하므로 처음 뽑는 수는 1, 9, 2 만 볼 수 있다. 따라서 1, 9, 2중에서 가장 큰 수를 골라서 제일 앞에 넣는다. 1개를 골랐으므로 j = 1 이 된다.
2. j = 1이고 2자리 수중 앞의 자리를 제외하고 1개의 수를 뽑아야 한다. 이 상황에서 뽑을 수 있는 수는 1, 9를 제외한 2, 4 중에서 가장 큰 수이다.
3. 따라서 처음 뽑은 수는 9이고 두 번째 뽑은 수는 4 여야 한다.

즉 n개의 자리를 가진 수 중에서 k개를 골라서 가장 큰 수를 뽑는 방법은 다음과 같다.

1. start : 0부터 end : n-j까지의 인덱스를 탐색하며 가장 큰 수(index)를 골라내서 제일 앞에 붙인다.
2. start : index + 1부터 end : n-j까지의 인덱스를 탐색하며 가장 큰 수(index)를 골라내서 그다음 붙인다.
3. 2번의 과정을 j가 0이 될 때까지 반복한다.

코드로 옮기면 다음과 같다.

전체 코드는 아래에서 볼 수 있다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string number, int k)
{
    string answer = "";
    int ans_size = number.size() - k;
    while (ans_size != 0)
    {
        int max = 0;
        int idx = 0;
        for (int j = 0; j <= number.size() - ans_size; j++)
        {
            if (number[j] - '0' > max)
            {
                max = number[j] - '0';
                idx = j;
            }
        }
        answer.push_back(number[idx]);
        for (int j = 0; j <= idx; j++)
            number.erase(number.begin());
        ans_size--;
    }
    return answer;
}

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42883

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

programmers.co.kr

문제 설명

어떤 숫자에서 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();
    }
}