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

https://programmers.co.kr/learn/courses/30/lessons/4288#

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

 

풀이

 

스택을 이용해서 풀이하는 경우들도 있긴 하지만 저는 인덱스를 이용해서 풀이하였습니다.

앞에서부터 삭제가능한 범위에서 가장 큰 수를 하나씩 선택해서 answer 문자열에 하나씩 추가하며 삭제해 나갑니다.

이를 k개 삭제시 까지 반복하거나 아니면 남길 수 있는 숫자수 (len - k 개)를 모두 남긴 경우 까지 반복합니다.

 

while문에서 k개를 모두 삭제한 경우, 뒤에 숫자를 더 붙여주어야 할 필요가 있습니다.

반대로 남길 수 있는 숫자 수를 모두 남긴 경우엔 뒤에 있는 숫자들을 삭제한다고 생각해야합니다.

따라서 뒤에 숫자를 추가로 붙이는 연산을 해주면 끝나는 문제입니다.

 

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int len = number.length();
        char maxN;
        int maxIdx = 0;
        int nowIdx = 0;
        int check = 1;
        int del = 0;
        
        while(del < k){
            maxN = '0';
            int cnt = -1;   //삭제한 숫자 수
            //앞에서부터 삭제가능한 범위 내에서 큰 숫자 찾기
            for(int i=nowIdx; i < k+check; i++){
                //'9'면 절대 삭제하지 않음
                if(number.charAt(i) =='9'){
                    maxN = number.charAt(i);
                    maxIdx = i;
                    cnt = i-nowIdx;
                    break;
                }
                if(number.charAt(i) > maxN){
                    maxN = number.charAt(i);
                    maxIdx = i;
                    cnt = i-nowIdx;
                }
            }
            answer += maxN;
            nowIdx = maxIdx+1;
            check++;        //삭제하지 않기로 선택한 숫자 수
            del += cnt;     //총 삭제 수
            
            //삭제를 숫자의 뒤에서 해야할 경우
            if(check > len-k)
                break;
        }
        //뒤에 더 추가해야할 숫자 수
        int left = len - k - check+1;
        for(int i = nowIdx; i < nowIdx+left; i++)
            answer += number.charAt(i);
        
        return answer;
    }
}