[프로그래머스] - 큰 수 만들기 Lv.2

 

문제

 

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

예를 들어 숫자 9124에서 수 두개를 제거하면 19, 12, 14, 92, 94, 24를 만들 수 있습니다.

이 중 가장 큰 숫자는 94 입니다.

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

 

1. StringBuilder변수를 생성한다.

2. max, index 변수를 초기화시키고 생성한다.

 

 

여기서 for 루프는 이중으로 도는데 주어진 문자열 number의 길이 - k 만큼 for문을 먼저 돌고 내부 for루프는 위에 선언한 index 부터 k+i까지 루프를 돈다. 

만약 1924가 number로 주어지고 k가 2일 경우

외부 for 루프에서 i는 0부터 2이전까지 돌 것이다. 결국 두 자리가 출력되고 그 두 자리 판별은 k+i 까지 루프를 돌면서 가장 큰 수를 찾아낸다. 

 

 

 

디버깅

 

내부 for루프 첫번째 들어왔을 경우

if문에서 max는 0이고 number에 가장 첫번쨰 문자열은 1이기 때문에 if문을 들어간다. 그렇게 max 값은 변경되고 index 값은 1로 변경될 것이다. -> 결국 index 값은 max보다 큰 값을 찾을 경우만 계속 변경된다. 그래서 내부 for문은 큰 수를 찾지 못하면 index는 그 자리에 멈춰서 존재한다.

다음 for루프를 돌 경우 number에 두번째 자리는 9이다. 첫번째와 두번째에서 둘 다 max가 변경되므로 index에는 값 변화가 일어난다.  

그렇게 내부 for문이 끝나면 StringBuilder에 max값이 append 되고 max값은 0으로 초기화된다. 

index 값은 2가 유지된다. ( 1, 9 를 만나며 2가 증가한 값임, j는 그런 index 값을 대입함)  여기서 max는 0이므로 한 번 더 if문을 들어간다. number는 2이기 때문에 

이 과정이 4에서 또 일어나 면서 결국 max는 4가 된다.

그렇게 결국 출력은 94

 

 

- return 해야 할 문자의 길이는 매개변수로 들어온 number의 길이에서 k만큼을 빼준 길이가 된다.

- 그래서 for문을 먼저 만들어야 할 문자의 길이만큼 반복을 함

- 이후 가장 큰 수를 탐색하여 StringBuilder에 붙혀주고 return 해주면 된다.

- index변수를 활용하여  k+i (는 number에 총 길이까지 간다) i는 number.length()-k이기 때문에 그럼

 

코드

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

 

 

 

참고-

 

https://jhhj424.tistory.com/32

 

[알고리즘] 프로그래머스 큰 수 만들기(Level 2) [자바/JAVA] 풀이- 개발하는 지토