문제
해결 방안 고민
•
처음에는 이렇게 생각을 했다.
◦
주어진 k를 활용하여 number로 만들 수 있는 수를 모두 리스트에 담기
◦
리스트 정렬 => 가장 큰 숫자를 문자열 형태로 출력
•
그러나 이렇게 접근하면 시간 복잡도에서 문제가 발생할 수 있음을 확인하였다.
해결 방법
•
이 문제는 그리디 알고리즘으로 해결해야 문제가 풀린다.
•
각 자리에 들어올 수 있는 가장 큰 수를 가져와서 문자열에 붙이는 방식으로 진행을 해야 가장 큰 수를 만들 수 있다.
4177252841 이라는 숫자가 입력이 되고 총 6자리의 큰 수를 구한다고 가정해보자.
첫 번째 자리를 구할 경우 뒤 문자 5개를 남겨두고 앞 문자열에서 가장 큰 수를 구하는 방식으로 구할 수 있다.
첫번째 자리
(41772) 52841
마찬가지로 두 번째 자리를 구할 경우 뒤 문자 4개를 남겨두고 앞 문자열에서 가장 큰 수를 구하는 방식으로 구할 수 있다. 다만, 이미 선정이 된 가장 큰 수 바로 다음부터 시작(start)해서 가장 큰 수를 뽑으면 된다.
두번째 자리
(17 725) 2841
이후에는 두 번째 방식과 같은 알고리즘으로 문제를 해결할 수 있다.
세번째 자리
(77 252) 841
네번째 자리
(725 28) 41
다섯번째 자리
(2528 4) 1
여섯번째 자리
(5284 1)
코드
•
코드 1 (실패) - 완전히 실패
package algo250312;
import java.util.*;
// 큰 수 만들기 - Lv2 (실패)
public class Pro42883 {
public String solution(String number, int k) {
String answer = "";
List<Integer> list = new ArrayList<>();
int start = 0;
int end = start + 1;
int length = number.length();
char[] arr = new char[length]; // 배열 선언
int idx = 0;
for (char c : number.toCharArray()) {
arr[idx++] = c;
}
StringBuilder sb = new StringBuilder();
while (start != length - 1) {
for (int i = 0; i < k - 1; i++) {
sb.append(arr[start]);
sb.append(arr[end]);
}
list.add(Integer.parseInt(sb.toString()));
sb = new StringBuilder();
if (end == length - 1) {
start++;
end = start + 1;
} else {
end++;
}
}
Collections.sort(list);
int size = list.size();
answer = String.valueOf(list.get(size - 1));
return answer;
}
}
Java
복사
•
코드 2 (실패) - 시간 초과
package algo250312;
// 큰 수 만들기 - Lv2 (실패)
public class Pro42883_2 {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder();
int idx = 0;
int max = 0;
int length = number.length();
for (int i = 0; i < length - k; i++) {
max = 0;
for (int j = idx; j <= k + i; j++) {
if (max < number.charAt(j) - '0') {
max = number.charAt(j) - '0';
idx = j + 1;
}
}
sb.append(max);
}
return sb.toString();
}
}
Java
복사
•
코드 3 (성공)
package algo250312;
// 큰 수 만들기 - Lv2 (성공)
public class Pro42883_3 {
public String solution(String number, int k) {
// 각 자리에서 최고로 높은 수가 나오는 경우 생각하기
String answer = "";
StringBuilder sb = new StringBuilder();
char[] arr = number.toCharArray();
int length = arr.length - k;
// 문자 비교 시작하는 인덱스 변수
int start = 0;
for (int i = 0; i < length; i++) {
char max = '0';
for (int j = start; j <= i + k; j++) {
// 가장 큰 수를 골라서 그 다음 인덱스를 시작 인덱스로 설정하기
if (arr[j] > max) {
max = arr[j];
start = j + 1;
}
}
// 가장 큰 문자를 String에 넣기
sb.append(max);
}
// k개의 수를 제거할 때 얻을 수 있는 가장 큰 숫자 구하기
answer = sb.toString();
return answer;
}
}
Java
복사
•
코드 4 (성공)
◦
Stack을 활용한 풀이도 있었다.
package algo250312;
import java.util.Stack;
// 큰 수 만들기 - Lv2 (성공)
public class Pro42883_4 {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
for (int i=0; i<number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
stack.pop();
}
stack.push(c);
}
for (int i=0; i<result.length; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}
Java
복사