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

 

문제링크: programmers.co.kr/learn/courses/30/lessons/42883

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

 

풀이

 

k개의 수를 제거한다는 것은 (number.length() - k)개의 수를 뽑는 것과 같다. 뽑아야 되는 숫자의 자릿수를 n이라고 하면, number에서 뒤에서부터 (n - 1)개의 수를 남겨두고 나머지 수 중에서 제일 큰 수를 뽑으면 된다. 다음 수는 방금 뽑은 수 다음부터 뒤에서 (n - 2)개의 수를 남겨두고 제일 큰 수를 뽑는다. 이를 n개 수를 뽑을 때까지 반복한다. 

 

n: 뽑아야 되는 숫자의 개수

picked: 이전에 뽑은 숫자의 index

 

number = "4177252841"일 때 풀이

• 6번째 자리
  => number 뒤에서 5개 수 제외 => "41772" => 최댓값 7 선택, picked = 2
• 5번째 자리
  => number 뒤에서 4개 수 제외 => "725" => 최댓값 7 선택, picked = 3
• 4번째 자리
  => number 뒤에서 3개 수 제외 => "252" => 최댓값 5 선택, picked = 5
• 3번째 자리
  => number 뒤에서 2개 수 제외 => "28" => 최댓값 8 선택, picked = 7
• 2번째 자리
  => number 뒤에서 1개 수 제외 => "4" => 최댓값 4 선택, picked = 8
• 1번째 자리
  => number 뒤에서 0개 수 제외 => "1" => 최댓값 1 선택, picked = 9

 

 

 

 

소스코드

 

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

테스트 결과

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)