![[프로그래머스,Level 2] 큰 수 만들기(JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fu8Fog%2FbtqT0unsEx0%2FJyBGzF4QvW3BqV5pCOi9EK%2Fimg.png)
- 첫 풀이
첫 풀이에서는 문제에서 제공하고 있는 예제의 경우를 자세히 읽지 않아 삽 좀 펐다. 1924에서 발생할 수 있는 가지 수를 보면, 각 자리의 숫자들의 순서는 정해져 있다는 사실을 알 수 있다. 즉, 1924에서 2와 4를 제거하더라도 1과 9의 순서는 유지되어 91은 불가능하고 19만 가능하다는 의미이다.
이를 알아차리고 다시 재귀를 이용해 풀어보려고 했다. 하지만 결과는 시간초과, 런타임 에러, 메모리 초과 등의 에러 파티였다. 이에 머리 아파 다른 분들의 풀이에서 힌트를 좀 얻었다.
- 정답 풀이
다른 분들의 풀이를 두루 살펴보면 스택을 사용하기도 하고 2중 반복문을 이용하기도 하는 등 다양한 풀이가 존재했다. 너무 복잡해 여러가지 글을 읽어보던 중, 만들어야 하는 자릿수에 대한 설명이 있는 것을 보고 힌트를 얻어 자릿수를 어떻게 활용할 지 생각해 보았다.
입출력 예 3의 경우를 보면, 4177252841과 k는 4가 주어지며, 문자열의 길이 10 - 4 = 6이기 때문에 6자리의 가장 큰 수를 만들어야 한다. 그리고 힌트를 통해 생각해 본 결과. 한 자릿수를 채우기 위한 범위를 아래처럼 나타낼 수 있었다.
| 1자리 | 2자리 | 3자리 | 4자리 | 5자리 | 6자리 |
| 41772 | 5 | 2 | 8 | 4 | 1 |
이 표가 의미하는 것은 6자리의 숫자를 만들 때 첫 번째 자리를 제외하면 남는 5자리의 숫자를 만들기 위해서는 5개의 숫자가 남아있어야 한다. 즉, 뒤의 52841 5개의 숫자는 문제에서 요구하는 결과를 반환하기 위해 꼭 남아 있어야 하는 범위이다. 그렇다면 첫 번째 자리는 이 5개의 숫자를 제외하고 41772에서 하나 정해야만 한다.
41772의 범위에서 첫 번째 7이 가장 크므로, 첫 번째 자리 수는 7이 되고 4,1,7은 기존의 number 문자열에서 제거한다.
그렇다면 다시 number는 7252841이 남게 되고 위의 과정을 다시 수행하면 아래와 같다.
| 1자리 | 2자리 | 3자리 | 4자리 | 5자리 | 6자리 |
| 7 | 725 | 2 | 8 | 4 | 1 |
한 자리를 채웠기 때문에 만들어야 하는 5자리 수 중 맨 뒤 4자리는 확보한 뒤, 나머지 수들에서 큰 값을 찾는다. 이러한 과정을 반복하면 문제가 원하는 답을 반환할 수 있다.
총 6자리의 숫자를 만드는 반복문 한 개와 각 자리수를 만들 때 문자열을 탐색하는 반복문 한 개로 2중 반복문을 사용하게 된다. 이때, 위처럼 탐색을 위한 범위는 총문자열의 길이 - (만들어야 하는 자리 수 - 1,2,3...) 식이다. 위의 예제로 보면 총문자열의 길이 = 10,7... (number 문자열은 계속해서 줄어든다,), 만들어야 하는 자리 수 = 10 - 4(k) = 6(고정 값), 첫 번째 자리는 1, 두 번째 자리는 2.... 와 같은 식이다.
마지막으로 이와 같은 방식으로 풀이를 진행하게 되면 테스트 케이스 10번에서 시간초과가 발생한다. 개인적인 생각으로 굉장히 넓은 범위에서 큰 값을 찾을 때, 첫 번째에서 9를 발견해 가장 큰 값을 찾은채로 나머지 범위를 탐색하게 되면 그만큼 시간이 걸리기 때문이라 생각되어서 9를 찾게되면 바로 해당 자릿수는 9로 잡아주었더니 해결되었다.
class Solution {
public String solution(String number, int k) {
StringBuilder answer = new StringBuilder();
// 가장 큰 값의 인덱스 정보.
int idx=0;
// 만들어야 하는 자리 수, 고정된 값.
int scope = number.length() - k;
// 1. 각 자리 수를 반복하는 반복문
for(int i =1;i<=scope;i++){
// 2. 최댓값 변수.
int max = Integer.MIN_VALUE;
// 3. 각 자리 수를 정하기 위해 정해진 범위를 탐색하는 반복문, 현재 문자열의 길이 - (만들어야 하는 자리 수 - 현재 만들고 있는 자리 수)
for(int j = 0; j<number.length() - (scope -i);j++){
// 4. 9는 바로 최댓값 갱신.
if((number.charAt(j) - '0') == 9) {
max = 9;
idx = j;
break;
}
// 5. 최댓값을 찾는다.
if(max < (number.charAt(j) - '0')){
max = number.charAt(j) - '0';
idx = j;
}
}
// 6. 찾은 최댓값을 StringBuilder에 이어 붙인다.
answer.append(max);
// 7. 최댓값의 인덱스 ~ 현재 문자열의 마지막까지의 범위를 새로운 문자열로 갱신한다.
number = number.substring(idx+1,number.length());
}
return answer.toString();
}
} 어렵다