[프로그래머스 Level.2] 큰 수 만들기 (탐욕법(Greedy)) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 탐욕법(Greedy) > 큰 수 만들기

 

 

문제 설명

 

 

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

 

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

 

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

 

 

제한 조건

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

 

입출력 예

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

 

 

 

나의 코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int start = 0;
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<number.length()-k; i++) {
            int max = 0;
            
            for(int j=start; j<=k+i; j++) {
                if(max < number.charAt(j)-'0') {
                    max = number.charAt(j)-'0';
                    start = j+1; 
                }
            }
            
            sb.append(max);
        }
        
        answer = String.valueOf(sb);
        
        return answer;
    }
}

 

풀이

1. 해당 문제는 주어진 String number에서 k개를 제외 했을 때 가장 큰 수를 만드는 것이다.
2. 우선 k개를 제외했을 때 큰 수를 만들기 때문에 구하는 수의 길이는 number.length() - k 가 된다.
3. 그렇기 때문에 StringBuilder를 생성하고 number.length() - k 만큼 반복하면서 한 개씩 수를 append 시키면 된다.
4. String number에서 k개의 수를 제외하고 그대로 뽑는 것이기 때문에 number에서 뽑을 때 k + i 인덱스를 넘어가서는 안된다. 왜냐하면 수를 뽑고 append 시키면 다음 append 시키는 수는 무조건 뒤에 있는 인덱스의 수를 뽑아야 하기 때문에 뽑을 만큼의 수가 남아있어야 하기 때문이다. 마지막 수를 뽑을 때는 i가 number.length - k -1이기 때문에 k + number.length - k -1 = number.length - 1 이기 때문에 마지막 index의 수를 뽑을 수 있게 된다.
5. 그리고 수를 뽑으면 다음 수는 무조건 그 뒤의 인덱스에 있는 수를 뽑아야 하기 때문에 시작 index를 저장하기 위해서 int형 변수로 start를 생성하고 수를 뽑을 때마다 뽑은 수의 index + 1로 start 변수에 다음 시작 index를 저장한다.
6. 이렇게 이중 for문을 돌면서 start ~ k+i 구간에서 가장 큰 수를 뽑아 StringBuilder에 number.length() - k개를 append 시킨 후에 String으로 변환하여 answer에 저장하고 리턴하면 된다.