[프로그래머스] 탐욕법(Greedy):큰 수 만들기-JAVA (자바)

[level 2] 큰 수 만들기 - 42883

문제 링크

성능 요약

메모리: 85 MB, 시간: 9529.70 ms

구분

코딩테스트 연습 > 탐욕법（Greedy）

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 03월 15일 17:11:54

문제 설명

어떤 숫자에서 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"

 

 

k번 비교할 수 있도록 구간을 나누어 0번 인덱스부터 하나씩 증가시키며 각 구간별로 가장 큰 값을 선택하여 정답 문자열에 추가한다.

풀이 방법

k번 비교할 수 있도록 구간을 나누어 0번 인덱스부터 하나씩 증가시키며 각 구간별로 가장 큰 값을 선택하여 정답 문자열에 추가한다.

number = "4177252841", k = 4를 예시로 생각해보자.

가장 큰 수 8을 맨 앞자리에 두어도, 뒤에 남은 수가 "41"로 "841" 세자리 수가 되면서 6자리수가 성립되지 못한다.

 

4

1

7

7

2

5

2

8

4

1

idx = 0, i = 0
최대값 = 7

4

1

7

7

2

5

2

8

4

1

idx = 3, i = 1, 이전 최대값 2번 인덱스 이하 제외
최대값 = 7

4

1

7

7

2

5

2

8

4

1

idx = 4, i = 2, 이전 최대값 3번 인덱스 이하 제외
최대값 = 5

4

1

7

7

2

5

2

8

4

1

idx = 6, i = 3, 이전 최대값 5번 인덱스 이하 제외
최대값 = 8

4

1

7

7

2

5

2

8

4

1

idx = 8, i = 4, 이전 최대값 7번 인덱스 이하 제외
최대값 = 4

4

1

7

7

2

5

2

8

4

1

idx = 9, i = 5, 이전 최대값 8번 인덱스 이하 제외
최대값 = 1

answer = "775841"

 

만약 최대값을 찾는 중 9가 나오게 되면 이는 무조건 가장 큰 수가 되기 때문에 효율성을 위해 바로 최대값을 추가하고 다음 반복으로 넘어간다

최종코드

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