프로그래머스 | LV.2 큰 수 만들기 - 그리디 문풀 (Java)

⬛ 프로그래머스 | LV.2 큰 수 만들기 - 그리디 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

마냥 쉽지 않았다.

제한 조건에서 데이터가 100만 까지 들어올 수 있다고 했기 때문에 문자열 구성을 DFS 완탐으로 하는 건 불가능하다고 생각헀고, 그리디 적으로 매번 최적의 값을 고르면서 answer 값을 구성해야겠다고 생각했다.

 

k개의 숫자를 빼서 만들 수 있는 가장 큰 값의 조합을 구해야 한다. 그리고 순서는 바꿀 수 없다.

4177252841 에서 k=4라면 10개의 숫자 중 4개를 뺀 6자리 숫자 조합으로 max 값을 구해야 하는 상황이다.

1) 첫 번째 자리를 고를 때 idx는 최대 (뒤에 5개 자리는 남겨둔 상태까지) 갈 수 있다.

41772 | 52841

첫번째 자리는 반드시 앞쪽 다섯개 중에 하나여야 한다. 따라서 7이된다.

2) 두 번째 자리는 앞서 첫 자리로 구한 값의 idx뒤부터 (뒤에 4개 자리는 남겨둔 상태까지) 갈 수 있다.

417 | 725 | 2841

따라서 725 중 7이 된다.

3) 세 번째 자리는 앞서 두번째 자리로 구한값의 idx 뒤부터 (뒤에 3개 자리는 남겨둔 상태까지) 갈 수 있다.

4177 | 252 | 841

따라서 5가 된다.

4) 네 번째 자리는 앞서 세 번째 자리로 구한값의 idx뒤부터 (뒤에 2개 자리는 남겨둔 상태까지 ) 갈 수 있다.

417725 | 28 | 41

따라서 8이 된다.

5) 다섯 번째 자리는 앞서 네 번째 자리로 구한 값의 idx 뒤부터 (뒤에 1개 자리는 남겨둔 상태까지) 갈 수 있다.

41772528 | 4 | 1

따라서 4가 된다.

6) 여섯 번째 자리는 앞서 다섯 번째 자리로 구한 idx 뒤부터 (뒤에 0개 남은 자리까지) 갈 수 있다.

따라서 1이 된다. 

이들을 조합한 값은 매번 잘린 범위에서 그리디적으로 최선의 max값을 선택해서 이어붙인 방식이다.

return 한 정답은 “775841”이 되는 것이다.

---

1차 시도 | String으로 값을 이어붙였을 때 10번이 시간초과가 떴다.

10번 시간초과

String은 immutable 하기 때문에 문자열 추가 연산 속도가 StringBuilder보다 많이 느리다고 한다. 

문자열 추가 연산이 많이 필요한 경우, StringBuilder를 사용하자

import java.util.*;
class Solution {
    //솔루션 함수 
    public String solution(String number, int k) {
        String answer = "";
        
        int st = 0;
        for(int i=0; i<number.length() - k; i++){ //i로 밀고 가는 건 최대 k뺀 값까지 
            char max = '0';
            for(int j=st; j<= i + k; j++){
                if(max < number.charAt(j)){
                    max = number.charAt(j);
                    st = j + 1;
                }
            }
            //여기서 max값 이어붙임 
            answer += max;    
        }
        
        return answer;
    }
}

---

💚 제출 코드

import java.util.*;
class Solution {
    //솔루션 함수 
    public String solution(String number, int k) {
       
        StringBuilder sb = new StringBuilder();
        
        int st = 0;
        
        for(int i=0; i<number.length() - k; i++){ //i로 밀고 가는 건 최대 k뺀 값까지 
            char max = '0';
            for(int j=st; j<= i + k; j++){
                if(max < number.charAt(j)){
                    max = number.charAt(j);
                    st = j + 1;
                }
            }
            //여기서 max값 이어붙임 
            sb.append(max);
        }
        
        return sb.toString();
    }
}