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

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

문제 풀이

이 문제는 2가지 접근법을 가지고 있습니다.

1. idx를 통해 반복하면서 앞에 idx위치보다 작은 값이 있는지 비교하는 방법

2. 앞에서부터 k만큼씩 끊어주면서 최댓값을 문자열에 붙여주는 방법

풀이 코드

1. idx를 통해 반복하면서 앞에 idx위치보다 작은 값이 있는지 비교하는 코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        StringBuilder sb = new StringBuilder(number);
        int idx = 0;
        
        while(idx < sb.length()-1 && k != 0) {
            idx ++;
            
            if(sb.charAt(idx-1) < sb.charAt(idx)){
                sb.deleteCharAt(idx-1);
                idx = 0;
                k--;
            }
        }
        
        if(k != 0){
            for(int i=0; i<k; i++)
                sb.deleteCharAt(sb.length()-1);
        }
        return sb.toString();
    }
}

2. 앞에서부터 k만큼씩 끊어주면서 최댓값을 문자열에 붙여주는 코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        for(int i=0; i<number.length() - k; i++) {
            int max = 0;
            for(int j = index; j<= k+i; j++) {
                if(max < number.charAt(j)-'0') {
                    max = number.charAt(j)-'0';
                    index = j+1;
                }
            }
            sb.append(max);
        }
        return sb.toString();
    }
}

 

<출처>

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

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