[Algorithm] 큰 수 만들기_Greedy
문제 설명
어떤 숫자에서 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 1924
k 2
return 94
number 1231234
k 3
return 3234
number 4177252841
k 4
return 775841
접근하기
- 처음엔 완전 탐색으로 풀려고 했다. 근데 9999일 경우 아주 최악이다.
- 몇 개의 숫자를 뽑는게 아니라 몇 개의 숫자를 제외한다는 점이 포인트다.👻
- 몇 개의 숫자를 뽑는거라면 순열을 이용할 수 있겠지만, 몇 개를 제외하고 거기서 최대를 구하고 이런 과정을 반복해야 정답에 도달한다.
- 결국, 몇 개를 제외하고 범위를 정하고 거기서 최대를 구하고 바로 그리디 문제다.
- 늘 문제를 푸는 시간보다 문제에 접근하는 방법을 찾는 시간에 더 많은 시간을 쏟는다...물론 중요하지만😖
Code
class Solution {
public String solution(String number, int k) {
int pos = 0;
char max;
StringBuilder answer = new StringBuilder();
if(number.charAt(0)=='0') return "0";
//len-k 갯수를 뽑기 위한 반복
for(int i=0; i<number.length()-k; i++){
max = '0';
//지정 범위 중 최대값을 뽑기 위한 반복
for(int j=pos; j<=k+i; j++){
if(max < number.charAt(j)){
max = number.charAt(j);
pos = j+1;
}
}
answer.append(max);
}
return answer.toString();
}
}
-
연산 속도를 위해 StringBuilder를 사용하였다.
-
왜지? 싶다면 String vs StringBuilder vs StringBuffer 이 글을 보자. 🤭
Author And Source
이 문제에 관하여([Algorithm] 큰 수 만들기_Greedy), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jaeyunn_15/Algorithm-큰-수-만들기Greedy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)