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

## \[level 2] 큰 수 만들기 - 42883

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/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" |

***

## 풀이 코드

```java
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`&#x20;
* 4번째 인덱스 `0` 부터 마지막 인덱스까지 중 가장 큰 수를 고른다. `2`&#x20;
* 결과는 `9002` 로 통과

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

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

***

## 돌아보기

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

***

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