[프로그래머스 Java] 큰 수 만들기 알고리즘

문제 설명

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

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

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

제한 조건

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

 

입출력 예

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

 

풀이 방법

위에 테스트 예제 중에 3번째 예제로 예를 들어 설명해드릴게요.

4

1

7

7

2

5

2

8

4

1

먼저 10개의 숫자 중 4개의 숫자를 제거해야하니 6개의 숫자의 조합을 찾아야합니다.

순서는 변경하지 못하니 저는 구간을 나눠서 최대값을 찾아줬습니다

구간은 길이-k 번 만큼 나눠줄거에요,

첫번째 구간인 0번째부터 k(k=4)번째에서 최대값을 찾아보면 아래와 같습니다.

0~4번째 숫자

4

1

7

7

2

이 중에서 큰 숫자 7을 뽑아낸 후 그 뒤(3번째)에 숫자부터 i+k(i=1)까지에서 다시 큰 수를 찾습니다.

 

3~5번째

7

2

이 중에서 또 큰 숫자 7을 뽑아내고 그 뒤에 숫자부터 i+k(i=2)까지의 구간을 확인해볼게요.

 

4~6번째

2

5

2

여기서는 5가 제일 크므로 뽑아줍니다. 그럼 그 뒤에 숫자는 6번째부터 확인하면 되겠죠?

 

6~7번째

2

8

8를 뽑고나면 8번째 9번째 숫자는 반드시 들어가야합니다. 따라서 4, 1 추가해주면 아래와 같이 나옵니다.

 

7

7

5

8

4

1

 

위 방법대로 소스 코드를 작성하면 아래와 같습니다.

 

자바 코드

class Solution {
    public String solution(String number, int k) {
        int pos = 0;
        char max;
    StringBuilder answer = new StringBuilder();
 
    if(number.charAt(0) == '0') return "0";
    for(int i = 0; i < number.length() - k; i++) {
        //문자 길이에서 k개 제거한 길이만큼 반복 ex. 6번(10개 중 4개 제거)
        max = '0';
        /* 0:1:2:3:4번째 자리 중에 큰 숫자 저장, 
        자리가 3일 경우 4:5 중에 큰 숫자 저장....
        (원래는 1:2:3:4:5) 확인해보지만 이미 뒤에 숫자가 들어갔기 때문*/
        for(int j = pos; j <= k + i; j++) {
                if(max < number.charAt(j)) {
                    max = number.charAt(j); 
                   pos = j + 1;
                }
        }            
        //숫자를 하나씩 덧붙여줌
        answer.append(max);
    }
        return answer.toString();
    }
}