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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "/"; // '/'의 아스키 코드값이 숫자(0~9)보다 작다.
    
    for (int i = 0; i <= k; i++) {
        if (answer[0] < number[i]) {
            answer[0] = number[i];
        }
    }
    
    return answer;
}

k만큼만 반복하는 이유는 number에서 k만큼 뺀 길이의 수를 반환해야 하는데, k를 넘어선 인덱스를 선택하면 조건에 맞지 않기 때문이다. 예를 들어, number = "1234"에 k=2가 주어졌다면, 4가 선택되면 안 되는 것처럼 말이다. 

---

이제 그 다음으로 큰 수를 넣어보자. 이때 다음으로 큰 수는 가장 큰 숫자 다음으로 나오는 수 중에서 선택해야한다. 이를 위해서 조건문 안에 선택한 수의 다음 인덱스를 저장하게 하자. 그리고, 다음 수를 구하기 위해서 k의 범위도 하나 증가시켜 줘야한다.

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

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int select = 0;
    int ans_i = 0;
    int lim_len = number.length() - k; // 반환해야할 수의 길이
    
    while (answer.length() < lim_len) {
        answer += "/";
        for (int i = select; i <= k; i++) {
            if (answer[ans_i] < number[i]) {
                answer[ans_i] = number[i];
                select = i + 1; // 선택한 수의 다음 인덱스를 저장
            }
        }
        k++;
        ans_i++;
    }
    
    return answer;
}

 

---

결과