큰 수 만들기

링크텍스트

문제 설명

1. number에서 k개의 숫자를 삭제했을 때 만들어지는 가장 큰 수 return
   1-1. 이때 number의 순서는 변하면 안된다.
   ex) 19를 삭제했을 때 24는 가능하지만 42 이런식으로 숫자 순서가 바뀌면 안된다는 뜻

문제 풀이 및 시행 착오

우선 보자마자 오케이 그리디~ 했음
이중 for문 쓰는 것도 알겠고.. 근데 범위 설정하는데 애먹었음

오답 코드

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        String answer = "";
        
        
        //뽑아야 하는 자릿수 만큼 반복
        for(int i=0; i<number.length()-k; i++) {
            char max = '0';
            for(int j=i; j<i+k+1; j++) {
                //큰 수 찾기
                if(max<number.charAt(j)) {
                    max = number.charAt(j);
                    
                }
                //효율성을 위해 제일 큰 수((9)라면 끝내버리기
                if(max == '9') {
                    break;
                }
            }
            
            answer += Character.toString(max);
        }
        return answer;
    }
}

결과

테스트 1
입력값 〉	"1924", 2
기댓값 〉	"94"
실행 결과 〉	실행한 결괏값 "99"이 기댓값 "94"과 다릅니다.
테스트 2
입력값 〉	"1231234", 3
기댓값 〉	"3234"
실행 결과 〉	실행한 결괏값 "3334"이 기댓값 "3234"과 다릅니다.
테스트 3
입력값 〉	"4177252841", 4
기댓값 〉	"775841"
실행 결과 〉	실행한 결괏값 "777888"이 기댓값 "775841"과 다릅니다.
테스트 결과 (~˘▾˘)~
3개 중 0개 성공

그냥 무지성으로 큰 수만 잔뜩 뽑아냈네????

원인은.. 내가 이중for문의 j를 i부터 시작해서 이다.
i부터 즉, 처음부터 검사를 시작하면 앞에서 뽑은 가장 큰 수도 포함해서 다시 검사를 하기 때문에 당연히 큰 수가 나오는 것이다.
그러므로 내가 뽑은 큰 수 바로 뒤의 수부터 다시 검사를 해야 한다.
int start를 만들어서 다시 작성하였다.

정답 풀이

1. 뽑아야 하는 자릿수(number.length()-k)만큼 반복
2. char형 max를 가장 작은 '0'으로 두고 가장 큰 수 찾기
   2-1. start부터 i+k+1까지 검사한다 = 뒤에 최소한의 숫자만 남겨놓고 앞에서 검사한다.
   2-2. 가장 큰 수를 찾으면 start는 그 뒤의 수로 갱신한다. = 이래야지 가장 큰 수끼리 중복이 안되고 그 뒤의 수부터 차례대로 큰 수를 찾을 수 있다.
3. 효율성을 위해 가장 큰 수인 9일 경우 break
4. String형으로 변환해서 answer 반환

연습장에 슥슥 풀면서 이해한 것도 메모메모~
일단, 3번째 예시로 풀었다.
연습장에 4177252841 적어놓고 네모칸 치면서 풀었다.
k는 4이므로 6자리를 뽑아야 한다.
그럼 뒤에 최소 5개를 남겨두고 앞의 41772 에서 가장 큰 수를 찾았다. -> 7
그 후 뒤로 한 칸 밀었다 = 17725에서 가장 큰 수를 찾되 start가 7이므로 72에서 가장 큰 수 찾기 -> 7
또 한 칸 밀기 = 77252에서 가장 큰 수를 찾되 start가 2이므로 252에서 가장 큰 수 찾기 -> 5
한 칸 밀기 = 72528에서 가장 큰 수를 찾되 start가 2이므로 28에서 가장 큰 수 찾기 -> 8
한 칸 밀기 = 25284에서 가장 큰 수를 찾되 start가 4이므로 4에서 가장 큰 수 찾기 -> 4
한 칸 밀기 = 52841에서 가장 큰 수를 찾되 start가 1이므로 1에서 가장 큰 수 찾기 -> 1
=> 775841

정답 코드

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        String answer = "";
        
        
        int start = 0;
        //뽑아야 하는 자릿수 만큼 반복
        for(int i=0; i<number.length()-k; i++) {
            char max = '0';
            for(int j=start; j<i+k+1; j++) {
                //큰 수 찾기
                if(max<number.charAt(j)) {
                    max = number.charAt(j);
                    start = j+1;
                }
                //효율성을 위해 제일 큰 수(9)라면 끝내버리기
                if(max == '9') {
                    break;
                }
            }
            
            answer += Character.toString(max);
        }
        return answer;
    }
}

정답!

• 중복이 안되게 뽑은 숫자 뒤부터 큰 수를 찾아야 한다는 점
• 6자리를 뽑아야 하면 뒤에 최소한 5개의 숫자를 두고 앞에서 큰 수를 찾아야 한다는 점 -> 난 이걸 네모칸으로 표시하면서 한 칸씩 뒤로 밀었다
• 뽑는 자릿수만큼 반복해야 한다는 점

코드는 간결한데 뭔가.. 논리적인 사고가 필요했던 문제인 것 같다.

---

예시 없으면 풀지도 몬함 허허