문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
나의 풀이
탐욕법문제. 나의 접근은 주어지는 숫자에서 몇 개의 수만 빼고 최대 값이니, 일단 자리수가 고정된다는 데서 시작했다. 주어진 문자에서 첫번째 자리에 올 수 있는 수자는 (주어진 문자 - k +1) 이기 때문에 그 중 가장 큰 숫자를 고른다. 만약 가장 큰 수와 같은 수가 있다면 젤 앞쪽에 오는 수를 선택한다. 그리고 다시 다음자리에 올 수 있는 범위를 정하고, 그중에 가장 큰 수를 고르길 반복한다. 포인트는 매번 젤 큰수를 선택할때 범위를 지정하는 것인데, 예를 들어 남은 숫자가 5자리이고 5개의 숫자를 골라야 한다면 매번 고를 숫자는 한 가지로 고정 될 것이다. 이번 문제는 말 그래도 그리디(탐욕법) 알고리즘이 무엇인지 느낌이 확 와닿는 문제였다.
코드
import java.util.*;
class Solution {
public String solution(String number, int k) {
String answer;
int length = number.length();
int count = length - k;
int left = 0;
int right = length - count;
int idx=0, max, temp;
StringBuilder sb = new StringBuilder();
while(count>0) {
max = -1;
for(int i = left; i<=right; i++) {
temp = number.charAt(i) - '0';
if(temp>max) {
max = temp;
idx = i;
}
}
sb.append(number.charAt(idx));
count--;
left = idx+1;
right = length - count;
}
return answer = sb.toString();
}
}'Algorithm > Programmers-Algorithm' 카테고리의 다른 글
| Programmers 조이스틱 java 풀이 (0) | 2020.08.18 |
|---|---|
| Programmers 힙(heap) 더 맵게 풀이 (0) | 2020.08.17 |
| Programmers 체육복 java 풀이 (0) | 2020.08.16 |
| Programmers 카펫 java 풀이 (0) | 2020.08.15 |
| Programmers 가장 큰 수 java 풀이 (0) | 2020.08.14 |