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

프로그래머스 > 코딩테스트 연습 > 탐욕법(Greedy) > 큰 수 만들기

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

프로그래머스

 

문제 설명

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

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

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

 

제한 조건

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

 

입출력 예시

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

---

나의 풀이 방법

number의 길이에서 k 를 뺀 것이 제거해서 만들 수 있는 answer의 길이다.

answer의 길이만큼 숫자를 하나씩 붙여서 가장 큰 숫자를 구한다.

number의 순서를 reverse할 수 없으니까 앞에서부터 큰 숫자를 가져올건데,

number의 시작과 끝이 범위가 되는 것이 아니라 answer의 길이를 남겨둔 인덱스 범위에서 큰 수를 찾는다.

범위 안에서 큰 숫자를 answer에 붙여주고 그 index부터 또 큰 숫자를 찾아가며 반복한다.

 

예를들면

"1231234" 와 k = 3 이 주어졌을 때 만들어야하는 answer의 길이는 4,

4만큼 반복하면서 answer를 만들어 준다.

처음 answer에 수를 붙일 때 

인덱스 0 ~ 3 까지의 수에서 큰 수를 찾아야 한다.

왜냐하면 만들어야 할 answer의 길이가 4라서 나머지 숫자 3개를 pick할 인덱스를 남겨놔야 하기 때문이다.

( 인덱스 4 ~ 6  - 3개 남겨놓기)

인덱스 범위는 for (int j = idx; j < number.length() - ansLen + answer.length() + 1 ; j++)

범위 안에서 가장 큰 수를 찾았다면 그 인덱스 번호를 remem 변수에 기억해두고 반복문을 나와서

answer에 가장 큰 수인 max 값을 더한다. 

remem 변수 안에 있는 인덱스 값에 하나를 더한 인덱스 부터 또 위의 과정을 반복해서 answer에 큰 수를 붙여가며 

가장 큰 수를 만들어 나간다. 

 

 

언어는 자바 ! 

 

# Issue 

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int ansLen = number.length() - k;
        int idx = 0;
        int remem = 0;
        for (int i = answer.length(); i < ansLen; i++) {
            char max = '0';
            for (int j = idx; j < number.length() - ansLen + answer.length() + 1 ; j++) {
                if (max < number.charAt(j)) {
                    max = number.charAt(j);
                    remem = j+1;
                }
            }
            idx = remem;
            answer += max;
        }
        return answer;
    }
}

테스트 10에서 시간 초과 문제가 발생했다.

고민끝에,,,,,, ,,

힌트를 좀 받았다,, ㅎㅎ 

 

범위 안에서 가장 큰 숫자인 9를 발견하면 더 인덱스를 탐색해서 그 다음 숫자로 넘어가서 인덱스를 낭비하거나 

의미없는 탐색을 하지 않고 바로 다음 숫자 탐색으로 넘어갈 수 있도록 하는 로직을 추가해주면 된다 !! 

if (number.charAt(j) == '9') {
    max = '9';
    remem = j+1;
    break;
}

 

 

완성 코드

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int ansLen = number.length() - k;
        int idx = 0;
        int remem = 0;
        for (int i = answer.length(); i < ansLen; i++) {
            char max = '0';
            for (int j = idx; j < number.length() - ansLen + answer.length() + 1 ; j++) {
                
                if (number.charAt(j) == '9'){
                    max = '9';
                    remem = j+1;
                    break;
                }
                if (max < number.charAt(j)) {
                    max = number.charAt(j);
                    remem = j+1;
                }
            }
            idx = remem;
            answer += max;
        }
        return answer;
    }
}