[프로그래머스] 큰 수 만들기 / JAVA

> 문제 설명 보기

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

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

> IDEA

순서를 바꿀수 없는 문자열 형태의 숫자 중 k개를 제거하여 ( = 문자열의 총 길이가 n일 때, n-k개를 선택하여) 가장 큰 수를 만드는 문제이다.

가장 큰 자릿수의 수를 골라야 가장 큰 수를 만들 수 있으므로 왼쪽부터 가장 큰 수를 고르면서, 항상 남아있는 숫자의 개수가 선택해야 하는 수의 개수 이상을 유지하면 된다.

 

예를들어 "1231234"의 경우, k = 3이라면 4개의 숫자를 선택해야 하는데

첫번째 숫자는 3개의 숫자를 남긴 "1231"에서 가장 큰 수를 골라 3이 되며

두번째는 첫번째 고른 숫자로부터 오른쪽엔 2개의 숫자를 남긴 "12" 중에 가장 큰 수를 골라 2가 되며

세번째는 두번째 고른 숫자로부터 오른쪽엔 1개의 숫자를 남겨 "3"중에 3이 되며

네번째는 세번째 고른 숫자로부터 오른쪽엔 0개의 숫자를 남겨 "4"중에 4가 된다.

 

따라서 "3234"를 반환하면 된다.

 

>Solution

class Solution {
    public String solution(String number, int k) {
        char maxVal;
        int pos = 0;
        StringBuffer sb = new StringBuffer();
        for(int cnt = number.length() - k; cnt > 0 ; cnt--){
            maxVal = '0';
            for(int idx = pos; idx < number.length() - cnt + 1; idx++){
                if(number.charAt(idx) > maxVal){
                    maxVal = number.charAt(idx);
                    pos = idx+1;
                }
            }
            sb.append(maxVal);
        }
        return sb.toString();
    }
}

 

String, StringBuilder, StringBuffer의 성능 차이를 알 수 있는 문제였다.

 

String은 immutable한 변수이기 때문에 한 번 선언되면 변하지 않고 String끼리 연산하여 String을 만들어 낼 때는 새로운 class를 생성하여 연산 결과를 할당하게 된다. 따라서 다수의 String 연산을 실행하게 되면 속도가 급격히 떨어진다.

 

StringBuilder와 StringBuffer는 내부적으로 배열 형태로 구현되어 새로운 문자열이 추가될 때, 해당 길이만큼 배열이 남아있다면 그대로 추가하여 사용하고, 모자라다면 두배의 크기로 배열을 할당하기 때문에 String보다 연산 속도가 빠르다.

다만 StringBuiler가 단일 쓰레드에서 연산속도가 더 빠르며 StringBuffer는 Thread-Safe하다.

 

> String 구현

>StringBuilder 구현

> StringBuffer 구현