문제 설명
어떤 숫자에서 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" |
구현
앞서 탐욕법에 대하여 정리해놓은 것처럼 탐욕법은 현재 볼 수 있는 대상 중에서 조건에 만족하는 가장 좋은 경우의 수를 찾는 문제이다.
해당 문제에 대한 해결법은 다음과 같다. 첫 번째 예에서 우리는 1924에서 2개의 수를 뽑아야 한다. 문제 설명에서 주어진 예시처럼 조합을 통하여 모든 경우의 수를 만들어내고 그중에서 가장 큰 수를 뽑아낼 수도 있다.
하지만 그런 식으로 문제를 푼다면 우리는 1924의 순서가 변하지 않는 상황에서 2개의 수로 만들 수 있는 가장 큰 수를 뽑아내야 하는데 그것을 코딩으로 옮기기가 과연 쉬울까? 하는 생각을 해보아야 한다.
그렇다면 접근 방법을 바꾸어 가장 앞에서부터 수를 보는 것이다.
1924에서 2개를 골라서 가장 큰 수를 뽑는 방법은 다음과 같다. (뽑아낼 개수 j = n-k)
- j = 2이고 2 자릿수를 만들어야 하므로 처음 뽑는 수는 1, 9, 2 만 볼 수 있다. 따라서 1, 9, 2중에서 가장 큰 수를 골라서 제일 앞에 넣는다. 1개를 골랐으므로 j = 1 이 된다.
- j = 1이고 2자리 수중 앞의 자리를 제외하고 1개의 수를 뽑아야 한다. 이 상황에서 뽑을 수 있는 수는 1, 9를 제외한 2, 4 중에서 가장 큰 수이다.
- 따라서 처음 뽑은 수는 9이고 두 번째 뽑은 수는 4 여야 한다.
즉 n개의 자리를 가진 수 중에서 k개를 골라서 가장 큰 수를 뽑는 방법은 다음과 같다.
- start : 0부터 end : n-j까지의 인덱스를 탐색하며 가장 큰 수(index)를 골라내서 제일 앞에 붙인다.
- start : index + 1부터 end : n-j까지의 인덱스를 탐색하며 가장 큰 수(index)를 골라내서 그다음 붙인다.
- 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; }문제 출처 : //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이다.