[프로그래머스][Greedy][Java][자바] 큰 수 만들기

by 비행학교브론즈 2024. 1. 5. 12:02

문제:

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

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

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

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

Greedy로 풀어야 하는 이유:

1. 2~1,000,000자리의 수 이므로 완전 탐색시 시간초과

설명되지 않은 제한 사항 : 자릿수는 변경할 수 없다.

코드선빵:

public String solution(String number, int k) {
    StringBuilder pickedSb = new StringBuilder();
    int pickedLength = number.length() - k;
    int start = 0;
    //뽑을 개수만큼 반복
    for (int i = 0; i < pickedLength; i++) {
        char max = '0';
        //뽑을 수의 범위에서 반복해서 수 찾기
        for (int j = start; j <= k + i; j++) {
            char thisNumber = number.charAt(j);
            if (thisNumber > max) {
                max = thisNumber;
                //다음 탐색범위는 가장 전의 가장 큰수 앞 부터
                start = j + 1;
            }
        }
        pickedSb.append(max);
    }

    return pickedSb.toString();
}

문제풀이:

1. ex): String number = "4177252841", int k = 4, String result = "775841"

2. K를 제거하는 대신 number.length() - K 의 숫자를 뽑는다.

3. "뽑아야 하는 범위"에서 "가장 큰 수 하나를 뽑는다" 를 "뽑는 개수 만큼" 반복한다 -> 가장 큰 수가 된다.

4. "뽑아야 하는 범위" 선정 (제거하지 않을 숫자 찾기)

String number = "4177252841", int k = 4, String result = "775841", length = 10
number의 길이는 10개이다.
6개를 뽑아야한다.
number중 제거 해야하는 범위인 0<= index <= 4 (0<= index <= k) 범위 이 중에서 숫자를 하나 뽑지 않는다면 5개의 숫자를 뽑아야하므로 반드시 뽑아야 함. (즉 이중에 뽑을 수가 있음)
이 범위에서 가장 앞자리가 될 수 하나를 뽑는다.
0 <= index <= 4 + 1 (0 <= index <= k + i) 범위에서 하나를 뽑지 않는다면 ...
모든 숫자를 뽑을 때 까지(6번) 반복한다.
뽑을 숫자 탐색 범위: (index < k + 현재 뽑은 개수 + 1) or (index <= k + 현재 뽑은 개수)

5. 재탐색 범위 설정: 전에 뽑은 숫자 다음.

실행 Example:

(괄호): 탐색 범위

Bold: 뽑은 숫자

~~취소줄~~: 이미 탐색한 숫자