[Programmers/JAVA] 큰 수 만들기 / 프로그래머스 코딩 테스트 연습

큰 수 만들기

 

---

문제 설명

 

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

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

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

---

예시

 

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

---

코드 해석 및 전체 코드

 

number의 길이에서 k만큼 뺀 다음, 각 자리 수의 최댓값 구하여 합치기

 

1. 반환할 StringBuilder 선언

String형으로 선언 시 테스트에서 시간 초과가 뜬다. 이를 해결하기 위해 StringBuilder 선언

 

2. 최댓값 저장할 문자형과 인덱스를 저장할 변수 선언 : char max, int cur

 

3. 이중 for문 반복하는데, 바깥쪽 for문은 반환할 문자열의 길이만큼 반복 : 0 ~ number.length() - k

 

3-1. 각 자리값을 구하는 것이므로 바깥쪽 for문을 반복할 때마다 max 0으로 초기화

 

4. 안쪽 for문은 반복을 시작할 값부터 k + i까지 반복

주어진 number가 1924이고, k가 2일때, 

10의 자리, 1의 자리를 구하게 된다. 

먼저 10의 자리를 구하는 과정에서 max는 9, cur은 1 + 1 = 2가 저장된다.

9의 이전의 인덱스의 요소는 사용할 수 없고 그 다음 인덱스부터 사용가능하므로

2가 저장된 cur부터 안쪽 for문이 반복되는 거다.

 

5. 안쪽 for문 반복이 끝나고 저장되어 있는 max가 해당 자릿수의 최댓값이므로 그 값을 반환값에 문자열을 붙이는 append() 메소드를 사용하여 붙임

 

6. 가장 큰 수를 구한뒤 문자열로 변환하는 toStirng() 메소드를 사용하여 반환

 

number = "1924",   k = 2,   number.length() - k = 2

i	j	max	cur	ret
0	0	1 > 0	1	""
0	1	9 > 1	2	""
0	2	9 > 2	2	""
0	3	9 > 3	2	""
1	2	2 > 0	3	"9"
1	2	4 > 2	4	"9", j for문 종료 --> "94"

 

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

 

---

github

programmers