[PGM_42883] 큰 수 만들기 (Java)

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 탐욕 알고리즘

1. 문제 이해

숫자 number와 지워지는 문자의 개수 k가 주어질 때 가장 큰 값으로 지워지게 만들어주는 경우를 구해주는 문제이다.

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

 

위 예시를 보면 알 수 있듯이 1924에서 2개의 수를 지웠을 때 가장 큰 값은 94이고, 1231234에서 3개의 수를 지웠을 때 가장 큰 수는 3234임을 알 수 있다.

 

2. 접근방법

문제는 굉장히 이해하기 쉽지만 막상 구현이 쉽지가 않다. 왜냐하면 number의 자리수가 최대 백만자리까지올 수 있는 경우를 계산해야하기 때문이다. 따라서 이 문제를 접근하기 위하여 우리는 인덱스로 접근을 시도하여야한다.

 

number의 길이가 100이라고 하고 k가 10이라고 하자. 그러면 결과값의 길이는 90이 된다. 그렇다면 우리는 10개의 지워질 값을 찾아주기 위해 그리디하게 앞에서부터 최대값을 찾아 지워주기만 하면 된다.

 

그 방법은 100자리의 숫자의 맨 앞 11자리의 숫자와 나머지 79 자리의 숫자로 나누어 주고, 11자리 숫자에서 최대값의 위치를 찾아주는 것이다. 만약 11자리의 숫자 중 최대값이 맨 끝 11번째 자리였다면, 앞에 10 자리를 지워준 값이 최대값이 되기 때문에 더이상 진행할 것 없이 문제를 해결한다. 하지만 만약 5번째 자리의 숫자가 최대값이라면 그 다섯번째 자리의 수는 첫번째 자리 수가 된다. 그리고 앞에 4자리는 지워진것으로 생각하고 뒤에 남은 것들로 다시 k개를 지울 때 까지 반복해주면된다.

-> 읽는 걸로는 도저히 이해하기 힘들수 있다.. 예시로 설명을 드리겠다.

 

문제의 예시를 예로 들어보겠다.

number는 4177252841 그리고 k는 4인 경우이다. 정답은 775841이다.

 

4177252841은 10 자리이다. 여기서 4자리를 지우면? 결과는 6자리이어야한다. 

그러면 이렇게 쪼개주는 것이다. 41772 52841

 

앞에 41772에서 최대값을 구해주면? 7이다.(첫번째로 나온 7로 생각하자.)

그러면 우리는 첫번째 자리의 수를 구해준 것이다. 바로 7이다.(이 부분이 이해안되면 우리가 지워야하는 개수가 4개인 것을 주목해라)

 

41 7 725 2841

우리는 현재 4와 1을 지워준 상태이며 최대값 7을 찾아준 상태이다. 그렇다면 우리가 앞으로 지울 수 있는 개수는 2개이다.

이것을 고려하여 7 이후로 3자리를 뽑아 최대값을 구해준다. 그렇게 되면 725 중 7이 선택되며 아무도 지워지지 않는다.

 

41 77 252 841

다음으로 우리는 252에서 고민을 하게 된다. 5가 최대 값이니 앞에 있는 2를 지워주면 된다.

 

41 77 25 28 41

마지막으로 숫자 하나만 지워주면 된다. 따라서 5 바로 뒤 2와 8을 선택해 최대값을 구해준다.

8이 최대값으로 선택되면 2는 지워지게 된다.

 

41 77 25 28 41

그러면 삭제를 희망한 개수만큼 삭제를 하였으므로 최종적인 결과인 775841이 나오게 된다.

구현코드

public class Solution {
    public String solution(String number, int k) {
        StringBuilder builder = new StringBuilder();

        int idx = 0;
        int max;
        for(int i = 0; i < number.length()-k; i++){
            max = 0;
            for(int j = idx; j <= i+k; j++){
                if(max < number.charAt(j)-'0'){
                    max = number.charAt(j)-'0';
                    idx = j+1;
                }
            }
            builder.append(max);
        }
        return builder.toString();
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)