[99클럽 코테 스터디 20일차 TIL] 프로그래머스 - 큰 수 만들기

99클럽 코테 스터디 20일차 TIL 입니다.

[level 2] 큰 수 만들기 - 42883

문제 링크

구분

탐욕법（Greedy）

문제 설명

어떤 숫자에서 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"

---

풀이 코드

import java.util.Arrays;

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        int len = number.length();
        char[] numbers = number.toCharArray();
        int cnt = len - k;
        int start = 0;
        while (cnt > 0) {
            char max = '0';
            for (int i = start; i <= len - cnt; i++) {
                if (numbers[i] > max) {
                    max = numbers[i];
                    start = i + 1;
                }
            }
            answer.append(max);
            cnt--;
        }
        
        return answer.toString();
    }
}

• Time: 7892.60 ms

• Memory: 92 MB

푸는데 정말 오래 걸렸다. 일단 풀이 방식 자체는 틀리지 않았으나 반복문을 어디서부터 어디까지 순회해야 하는지 해당 조건을 찾는데에 오래 걸렸고 char 배열이 아닌 String 배열로 푸는 경우엔 크기 비교를 위해 Integer.parseInt() 메소드를 써서 그런지 시간 초과가 발생하기도 했다. 내가 생각한 풀이 방식은 아래와 같다.

• 6개의 숫자로 이루어진 문자열 "190002" 에서 2개를 제거했을 때 가장 큰 수를 구한다.

• "190002" 에서 2개를 제거한 4개 문자를 고르는 것과 동일하다.

• 4개 문자를 고를 땐 문자 순서를 지켜야 한다. 단순히 4개 문자를 골라서 가장 큰 수는 9210 이지만 문자 순서에 맞게 해야 하기 때문에 9002 가 나와야 한다.

• 첫번째 큰 수를 고를 땐 문자의 뒷 순번이 3개 이상 남는 숫자 안에서 골라야 한다. 그래야 그 이후에 남은 3개 문자를 고를 수 있기 때문이다. 따라서 190 에서 가장 큰 수를 골라야 한다. 9

• 가장 큰 수를 고른 뒤에는 가장 큰 수의 다음 숫자부터 문자의 뒷 순번이 2개 이상 남는 숫자 안에서 고르면 된다. 9 의 다음 숫자인 0 부터 2개 이상이 남는 3번째 인덱스의 0 까지 중 가장 큰 수를 고른다. 2번째 인덱스 0

• 3번째 인덱스 0 부터 4번째 인덱스 0 까지 중 가장 큰 수를 고른다. 3번째 인덱스 0

• 4번째 인덱스 0 부터 마지막 인덱스까지 중 가장 큰 수를 고른다. 2

• 결과는 9002 로 통과

처음 풀이할 때는 split() 함수를 통해 문자열 배열을 생성하고 문자열을 하나하나 정수형으로 변환하여 max 값을 구했다. 하지만 초기 max 의 값을 정수형 0 으로 두는 바람에 통과하질 못했었다. 왜냐하면 0 값이 들어오게 되면 if (numbers[i] > max) 조건문을 타지 않아 인덱스 값이 계속 그대로 있게 되면서 이미 뽑은 숫자도 다시 뽑게된다.

따라서 max 의 초기 값을 -1 로 두게 되면 해결이 가능하다.

---

돌아보기

풀이 방법 생각하고 왜 스스로의 풀이 방법을 100% 믿어야 한다고 했는지 알겠다. 정말 많이 헤맸다.

---

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL