[프로그래머스] 큰 수 만들기 - Java

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

프로그래머스

 

⭐️ 중요 포인트

1. number의 자리수는 100만, k도 100만. 그렇다면 대충 계산해봤을 때, 시간 복잡도는

(1) 기본적으로 모든 number을 반복하는 수 O(N / 2)

(2) 대략 계산해보면 k = number/2일 때 최악일 것 같음... 이유는 k가 절반이면 아래와 같이 그리디로 푼다고 가정했을 때, 특정 구간(lastIdx ~ k + cnt)에서 가장 큰 값을 찾는 시간복잡도는 O(N) -> 최악의 시나리오는 앞에서 계속 선택되어서 lastIdx는 1씩 증가하면서 구간은 ([0 ~ number / 2] 부터 [number / 2 ~ number])까지 반복하는 것

그래서 위 두 상황을 더하면 O(N^2 / 4) 대충?.. -> 그리디로 풀었을 때임

(3) 최적화를 위해 selectArr의 남은 길이와 numberArr의 남은 길이가 같다면 -> 더이상 뺄 k가 남아있지 않음.

그럼 뒤에는 더이상 비교하지 않고 탈출. (사실 푼 후에 다시 생각해보면 마지막 한 번만 빠르게 탈출하는 듯 하다... 필요 없는 코드일듯?..)

 

위 상황을 k를 제외하고 완탐으로 모든 조건을 검사해서 푼다면 아마 시간초과가 날 것...

 

따라서 그리디로 선택. 풀이는 아래 사진을 참고

 

 

import java.util.*;

class Solution {
    
    static String answer;
    static char[] numberArr;
    static char[] selectArr;
    
    public void solve(int k) {
        int lastIdx = -1;
        int cnt = 0;
        
        while (cnt != numberArr.length - k) {
            
            // arr의 남은 길이와 answer의 남은 길이가 같다면 자동으로 완성시키고 탈출
            if (selectArr.length - cnt == numberArr.length - (lastIdx + 1)) {
                for (int i = lastIdx + 1; i < numberArr.length; i++) {
                    selectArr[cnt++] = numberArr[i];
                }
                break;
            }
            
            // 범위 안에서 큰 값 찾기
            int maxNum = numberArr[lastIdx + 1];
            int maxIdx = lastIdx + 1;
            for (int i = lastIdx + 2; i <= k + cnt; i++) {
                if (maxNum < numberArr[i]) {
                    maxNum = numberArr[i];
                    maxIdx = i;
                }
            }
            selectArr[cnt++] = numberArr[maxIdx];
            lastIdx = maxIdx;
        }
        
        answer = new String(selectArr);
        
    }
    
    public String solution(String number, int k) {
        // -- init --
        answer = "";
        numberArr = number.toCharArray();
        selectArr = new char[numberArr.length - k];
        // -- init --
        
        solve(k);
        
        return answer;
    }
}