[프로그래머스 알고리즘] 큰 수 만들기 (Level 2)

문제

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

접근

총 길이에서 k개를 지워야 한다. 만약 k = 3 이고 123456을 지운다 하면 앞에 123을 지우면 된다.
직관적으로, 맨 앞에서부터 4개씩 탐색하면서 최댓값을 뽑아내면 쉽다. 1234에서 4, 2345에서 5, 3456에서 6 이렇게...
예를 들면, k = 3 이고 123619를 위 알고리즘대로 수를 뽑는다 하면 1236에서 6을 뽑고, 2361에서 6은 이미 뽑았으므로 뽑을 수 없고, 3을 뽑게 되는데, 이렇게 되면 정답인 619와 다르게 된다.
따라서, 만약 어떤 수를 선택했으면, 그보다 앞에 있는 수는 고를 수 없다.

코드 (시간초과)

import java.util.*; 
//
class Solution {        //앞에서부터 k+1개씩 탐색하며 최댓값을 answer에 + 해준다.
    public String solution(String number, int k){
        String answer = "";
        int max = 0;
        int lastIdx = -1;
//        
        for(int i = 0; i < number.length() - k; i++){
            max = 0;
            for(int j = lastIdx + 1; j <= i + k; j++){            //k+1개씩 탐색하면서 최댓값 뽑기 
                int curr = (int)(number.charAt(j) - '0');
                if(curr > max){
                    max = curr;
                    lastIdx = j;            //현재 최댓값을 뽑아서 문자열에 붙였으면, 그 앞의 수들은 못씀. 
                }
            }
            answer += Integer.toString(max);    
        }
//        
        return answer;
    }
}

시간 초과가 떴다. 찾아보니, String을 다룰 때, String은 불변객체로, +를 이용하여 String을 조작하면 계속 새로운 공간을 할당하고 복사 붙여넣기 하여 성능이 매우 떨어지게 된다는 단점이 있다. 따라서 가변 객체인 StringBuilder를 사용해야 한다.

StringBuilder

• 객체 생성

StringBuilder sb = new StringBuilder();

• 값 더하기

sb.append("");
sb.append("abc");

• String에 저장

String str = sb.toString();

코드 (정답)

import java.util.*; 
//
class Solution {        //앞에서부터 k+1개씩 탐색하며 최댓값을 answer에 + 해준다.
    public String solution(String number, int k){
        String answer = "";
        int max = 0;
        int lastIdx = -1;
        StringBuilder sb = new StringBuilder("");
//        
        for(int i = 0; i < number.length() - k; i++){
            max = 0;
            for(int j = lastIdx + 1; j <= i + k; j++){            //k+1개씩 탐색하면서 최댓값 뽑기 
                int curr = (int)(number.charAt(j) - '0');
                if(curr > max){
                    max = curr;
                    lastIdx = j;            //현재 최댓값을 뽑아서 문자열에 붙였으면, 그 앞의 수들은 못씀. 
                }
            }
            sb.append(Integer.toString(max));    
        }
//        
        answer = sb.toString();
//        
        return answer;
    }
}