[프로그래머스] 큰 수 만들기 (자바)

프로그래머스 큰 수 만들기

문제풀이

문제의 제한 조건에서 1,000,000 개의 길이의 문자열까지 입력이 가능하므로 완전 탐색으로는 문제를 해결할 수 없다
-> 시간 복잡도에서 걸러질듯하다

이 문제는 Greedy 알고리즘으로 문제를 해결할 수 있다.

각 자리에 들어올 수 있는 가장 큰 수를 가져와서 문자열에 붙이는 식으로 가장 큰 수를 만들 수 있다.

그러면 어떤식으로 접근을 할까?

내 경험상 그리디 알고리즘은 사고방식을 반대로 생각해야 접근을 수월하게 할 수 있
었다.

예를 들어, 4177252841 이라는 숫자가 입력이 되고 총 6자리의 큰 수를 구한다고 가정해보자

첫 번째 자리를 구할 경우 뒤 문자 5개를 남겨두고 앞 문자열에서 가장 큰 수를 구하는 방식으로 구할 수 있다.

첫번째 자리
(41772) 52841

마찬가지로 두 번째 자리를 구할 경우 뒤 문자 4개를 남겨두고 앞 문자열에서 가장 큰 수를 구하는 방식으로 구할 수 있다. 다만, 이미 선정이 된 가장 큰 수 바로 다음부터 시작(start)해서 가장 큰 수를 뽑으면 된다.

두번째 자리
(17 725) 2841

이후에는 두 번째 방식과 같은 알고리즘으로 문제를 해결할 수 있다.

세번째 자리
(77 252) 841

네번째 자리
(725 28) 41

다섯번째 자리
(2528 4) 1

여섯번째 자리
(5284 1)

최종 자바 코드는 다음과 같다.

구현코드

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        // 그리디 알고리즘
        // 각 자리에서 최고로 높은 수가 나오는 경우를 생각하기
        
        String answer = "";
        StringBuilder answerBuilder = new StringBuilder();

        
        char[] array = number.toCharArray();
        
        int len = array.length - k;
        
        // 문자 비교를 시작하는 인덱스를 나타내는 start 변수 
        int start = 0;

        for(int i =0; i<len; i++){
            char max = '0';
            for(int j = start; j <= i + k; j++){
                // 가장 큰수를 골라서 그 다음 인덱스를 시작 인덱스로 설정하기 
                if(array[j] > max){
                    max = array[j];
                    start=j+1;
                }
            }
            // 가장 큰 문자를 String에 넣어주기
            answerBuilder.append(Character.toString(max));
        }
        
        // k개의 수를 제거할 때 얻을 수 있는 가장 큰 숫자를 구하려 한다 
        answer = answerBuilder.toString();
        return answer;
    }
    
}

그리디 알고리즘은 부분 문제의 가장 최적의 해답을 찾는 방식이다. 이 접근을 하기 위해서는 부분 문제를 얼마나 잘 설정하느냐가 중요할 것 같다.
부분 문제를 설정할 때 다양한 경우의 수를 생각해내서 가장 간결한 부분 문제를 설정해야 빠른 시간안에 문제를 해결할 수 있을 것 같다.