큰 수 만들기(그리디, 탐욕법)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

---

1. 문제 설명

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

 

문제!!

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

 

제한사항

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

 

예시

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"
"9999"	2	"99"

---

2. 문제풀이

최종적으로 나오는 문자열의 길이는 원래길이 - k 값입니다. 그래서 이만큼 반복을하는 반복문을 작성해줍니다.   이제 이중에서 큰숫자를 뽑는 방식을 찾아야 합니다. 어디까지 계산을 해야할까요?   #1924를 예로 들어보겠습니다. 1. k값이 2이므로 4-2 = 2글자가 출력됩니다.   2. 그렇다면 앞에서 (0, 1, 2)2까지 검사를해서 큰수를 찾으면 됩니다. 1924에서 앞에서 2까지인 부분은 192 입니다. 이중에서 가장 큰 숫자는 9가 됩니다.   3. 9를 사용했으므로 검사는 9의 뒤부터 하게됩니다. 한번 뽑았으므로 뒤에 검사하는 부분을 하나 증가시킵니다. 24가 남게되고 이중에서 가장 큰 숫자는 4입니다.   4. 따라서 정답은 94가 됩니다.   #4177252841를 두번째 예시로 들어 보겠습니다. 1. k값이 4이므로 10 - 4 이므로 6글자가 나오게 됩니다.   2. 그리고 앞에서 (0, 1, 2, 3, 4)4까지 검사를 해야하므로 41772 중에서 제일 큰 숫자를 찾습니다. 7이 제일 큰 숫자이므로 이 값을 저장합니다.   3. 다음검사는 7뒤에부터 검사를 하는데 아까 검사한 위치에서 하나를 증가시킵니다. 725 중에서 제일 큰 숫자는 7입니다. 7이 제일 큰 숫자이므로 이 값을 저장합니다.   4. 다음검사는 7뒤에서부터 검사를 하고 아까 검사한 위치에서 하나를 증가시킵니다. 252 중에서 제일 큰 숫자는 5입니다. 5가 제일 큰숫자이므로 이값을 저장합니다.   5. 다음검사는 5뒤에서부터 검사를 하고 아까 검사한 위치에서 하나를 증가시킵니다. 28 중에서 제일 큰 숫자는 8입니다. 8이 제일 큰숫자이므로 이 값을 저장합니다.   6. 이후 뒤에나오는 숫자는 1개씩밖에 없으므로 그대로 뒤에 붙습니다. 따라서 정답은 775841이 됩니다.

 

---

3. 소스코드

 

3.1 주석없는 코드

#include <iostream>
#include <string>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    for (int j = 0, index = -1; j < number.length() - k; j++) {
        char max = 0;
        for (int i = index + 1; i <= k + j; i++) {
            if (max < number[i]) {
                index = i;
                max = number[i];
            }
        }
        answer += max;
    }
    return answer;
}

3.2 주석있는 코드

#include <iostream>
#include <string>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    //필요한 글자수만큼 반복하기
    for (int j = 0, index = -1; j < number.length() - k; j++) {
        char max = 0;
        //앞에서 남겨야 되는 숫자 중에 제일 큰수 체크
        for (int i = index + 1; i <= k + j; i++) {
            if (max < number[i]) {
                index = i;
                max = number[i];
            }
        }
        //제일 큰수를 정답에 추가
        answer += max;
    }
    return answer;
}

3.3 테스트 코드 추가

#include <iostream>
#include <string>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    //필요한 글자수만큼 반복하기
    for (int j = 0, index = -1; j < number.length() - k; j++) {
        char max = 0;
        //앞에서 남겨야 되는 숫자 중에 제일 큰수 체크
        for (int i = index + 1; i <= k + j; i++) {
            if (max < number[i]) {
                index = i;
                max = number[i];
            }
        }
        //제일 큰수를 정답에 추가
        answer += max;
    }
    return answer;
}
 
void print(string number, int k, string answer){
    string t = solution(number, k);
    if (t == answer)    cout << "정답" << endl;
    else    cout << "틀림" << endl;
}
 
int main() {
    print("1924", 2, "94");
    print("1231234", 3, "3234");
    print("4177252841", 4, "775841");
    print("9999", 2, "99");
    return 0;
}

---

4. 결과