설명
프로그래머스의 큰 수 만들기 문제다.
문자열로 이루어진 숫자가 주어질 때 주어진 갯수만큼 글자를 빼서 만들 수 있는 가장 큰 수를 찾는 것이 목적이다. 예를 들어 "1924"가 주어지고 2개의 숫자를 뺀다면 "94"가 만들 수 있는 가장 큰 숫자가 될 것이다. 비슷하게 "1231234"에서 3개의 숫자를 뺀다면 "3234"가 된다. 마치 stable한 정렬처럼 당연히 숫자의 순서는 유지되어야 한다.
풀이
완전탐색(실패)
처음으로 시도했던 풀이는 숫자를 하나씩 빼 보면서 모든 조합을 찾고 자바의 Comparator를 이용하여 비교 및 정렬하여 제일 큰 값을 찾는 과정을 빼야 하는 숫자의 갯수만큼 반복하는 방식이었다.
예를 들어 두 개를 빼는 "1924"라면 한 숫자를 뺀 경우인 "924", "124", "194", "192" 네 가지를 비교해서 가장 큰 "924"를 선택한 후 다시 한 숫자를 뺀다. 그러면 얻을 수 있는 "24", "94", "92" 중 가장 큰 "94"를 선택하면 답이 된다. 이렇게 k번 숫자를 빼서 조합하고 가장 큰 값을 찾는 방식인 것이다.
import java.util.*;
import java.util.stream.*;
class Solution {
public String solution(String number, int k) {
// 문자를 빠르게 비교하기 위해 char형 배열로 변환.
char[] numbers = number.toCharArray();
// 문자열(char형 배열)을 비교하는 Comparator 정의.
Comparator<char[]> bigNumberStringComparator = new Comparator<>() {
// 문제에서는 백만 자리의 정수까지 주어질 수 있음.
// 일반적인 방법으로는 비교가 불가능하여 한 글자씩 비교.
// ex) "1234", "1432"를 비교하는 경우.
// 1st: "1"과 "1"을 비교. 동일하므로 계속 진행.
// 2nd: "2"와 "4"를 비교. "4"가 더 크기 때문에 탐색 종료.
@Override
public int compare(char[] s1, char[] s2) {
for(int i=0;i<s1.length;i++) {
if(s1[i] == s2[i]) {
continue;
}
// 내림차순으로 정렬.
return s2[i] - s1[i];
}
// 모든 숫자가 동일하다면 0 반환.
return 0;
}
};
// k개의 숫자를 빼야 하므로 k번 반복.
while(k-- > 0) {
// 현재 차례에서 조합된 정수 문자열을 저장하는 배열 생성.
// 매 번 한 글자씩 줄어들기 때문에 문자열을 담는 배열의 크기는 1 감소.
char[][] candidates = new char[numbers.length][numbers.length-1];
// 각 글자를 뺀 조합을 배열에 저장.
for(int i=0;i<numbers.length;i++) {
// 현재 글자를 뺀 문자열을 배열에 저장.
// ex) "1924"의 경우 "1"을 뺀 "9", "2", "4"를 배열에 저장.
// 다음 차례에는 "9"를 뺀 "1", "2", "4"를 배열에 저장.
// 이렇게 모든 글자에 대해 반복하는 과정.
char[] candidate = new char[numbers.length - 1];
int pointer = 0;
for(int j=0;j<numbers.length;j++) {
if(i == j) continue;
candidate[pointer++] = numbers[j];
}
candidates[i] = candidate;
}
// 배열에 저장된 문자열을 비교, 가장 큰 문자열을 탐색 문자열로 대입.
// ex) "1924"의 경우 "924", "124", "194", "192" 조합이 있음.
// 이 중 가장 큰 "924"를 탐색 문자열(numbers)로 갱신
// 다음 차례에는 "924"에서 한 글자씩 빼서 탐색하게 됨.
Arrays.sort(candidates, bigNumberStringComparator);
numbers = candidates[0];
}
// k개의 숫자를 빼고 남은 가장 큰 정수 문자열을 String으로 반환.
StringBuilder sb = new StringBuilder();
for(int i=0;i<numbers.length;i++) {
sb.append(numbers[i]);
}
return sb.toString();
}
}하지만 이 풀이는 실패했는데 시간 초과와 메모리 초과가 가장 큰 문제였다. 백만 자리의 숫자가 있다면 char[][] candidates = new char[numbers.length][numbers.length-1]; 구문에서 1,000,000 * (1,000,000 - 1) 크기의 배열이 생성되기 때문에 메모리를 너무 많이 잡아먹게 되는 것이다. 실제로 에러가 발생하기 바로 전의 테스트 케이스가 메모리를 약 350MB 정도 소모했던 걸로 기억하는데 백만 자리의 숫자가 주어졌다면 이보다 더 메모리가 요구되었을 것이고 당연히 올바른 풀이는 아니란 것을 알 수 있었다.
게다가 한 글자를 뺀 문자열을 char 배열로 복사하는 과정에서 이중 반복문으로 인한 O(N^2) 시간 복잡도가 계산됐기 때문에 시간 초과가 발생하는 것도 당연한 결과였다.
스택 #1(성공)
위의 완전탐색 풀이도 처음엔 String으로 했다가 시간 초과, 메모리 초과가 발생해서 char 배열로 변환했으나 결과는 동일했었다. 그래서 알고리즘의 문제라고 판단하고 질문 게시판을 둘러보는데 스택을 사용하라는 말이 여기저기서 보였다.
이 때는 완전 탐색 풀이에 너무 몰두해서 항상 모든 조합을 확인하고 비교해야 한다는 생각에 갇혀 있었기 때문에 가장 큰 숫자를 찾는 Greedy 문제에서 스택을 어떻게 쓸 수 있을지 감이 잡히지 않았다.
그러다가 든 생각은 맨 처음 글자부터 숫자를 한 글자씩 스택에 삽입하며 이전에 넣은 숫자가 현재 숫자보다 작다면 이를 빼고 현재 숫자를 넣으면 될 것 같다는 것이다. "1924"를 예로 들어보면 다음과 같다.
- 스택이 비어있으므로 "1"을 삽입한다.(["1"])
- 다음 글자 "9"는 "1"보다 크므로 "1"을 빼고 "9"를 삽입한다.(["9"])
- 다음 글자 "2"는 "9"보다 작으므로 삽입한다.(["9", "2"])
- 다음 글자 "4"는 "2"보다 크므로 "2"를 빼고 삽입한다.(["9", "4"])
- 스택에 남아있는 숫자를 조합하면 가장 큰 조합이 된다.("94")
항상 이전보다 큰 숫자를 우선으로 삽입하는 Greedy한 특성을 만족시키기도 하고 스택에 삽입되는 순서대로 숫자 문자열을 만든다면 큰 숫자가 먼저 삽입되어야 더 큰 정수를 만들 수 있다는 점을 생각하면 올바른 풀이일 것이다.
"54..."는 "53..."보다 크기 때문에 현재 자릿수에 더 큰 숫자가 들어올 수 있다면 이를 빼고 더 큰 숫자를 넣는 과정을 스택의 pop 후 push로 구현할 수 있다고 생각하여 다음과 같은 코드를 구현하였다.
import java.util.*;
import java.util.stream.*;
class Solution {
public String solution(String number, int k) {
// 참조가 자주 일어나기 때문에 char 형 배열로 변환.
char[] numbers = number.toCharArray();
// 문자열을 구축할 스택.
Stack<Character> stack = new Stack<>();
// 몇 개의 숫자를 뺐는지 확인하기 위한 카운터.
int count = 0;
// k개의 숫자를 뺄 때까지 반복.
while(count < k) {
// 한 번도 삭제가 일어나지 않은 경우를 확인하기 위한 플래그.
// 숫자들이 내림차순으로 정렬된 경우 삭제가 일어나지 않음.
// 이 경우 현재 숫자 조합이 가장 큰 정수 문자열이라는 것을 의미.
// 이 경우 문자열 크기를 맞추기 위해 뒤의 숫자를 추가적으로 제거.
boolean removed = false;
// 숫자 문자들을 읽으면서 스택 작업.
for(char n: numbers) {
// 처음 글자라면 단순히 스택에 삽입.
if(stack.empty()) {
stack.push(n);
continue;
}
// 스택을 확인해서 현재 숫자보다 작은 숫자면 제거.
// 이때 스택은 비어있지 않아야 함: !stack.empty()
// 그리고 뺄 수 있는 숫자의 갯수를 초과하면 안됨: count < k
// 마지막으로 반복문으로 해당되는 숫자는 전부 삭제해야함.
// 그래야 greedy하게 얻은 현재의 최댓값이 전체의 최대값이 됨.
while(!stack.empty() && stack.peek() < n && count < k) {
removed = true;
stack.pop();
count++;
}
// 스택에 현재 숫자를 삽입.
stack.push(n);
}
// 예를 들어 "54321"처럼 아무런 숫자도 지워지지 않은 경우
// 지워야 하는 갯수만큼 뒤에 있는(낮은 자리수) 숫자를 삭제.
if(!removed) {
// 이때도 여전히 지울 수 있는 한도를 초과하면 안됌.
while(count++ < k) {
stack.pop();
}
}
// 스택에 남아있는 숫자들을 조합해서 문자열로 변환.
StringBuilder sb = new StringBuilder();
while(!stack.empty()) sb.append(stack.pop());
// 스택은 역순이므로 reverse 메서드로 반전.
numbers = sb.reverse().toString().toCharArray();
}
// 최종적으로 남은 숫자들을 조합해서 가장 큰 정수 문자열을 생성.
StringBuilder sb = new StringBuilder();
for(char c: numbers) {
sb.append(c);
}
return sb.toString();
}
}완전 탐색보다 훨씬 더 빠르고 적은 메모리로 아무런 문제 없이 통과할 수 있었다.
350MB가 나오던 풀이가 50MB로 줄어들고 1300ms가 2ms로 줄어든 것을 보니 방대한 데이터를 다룰 때 알고리즘의 중요성을 체감할 수 있었던 경험이었다.
스택 #2(성공)
그런데 위의 풀이는 완전 탐색 풀이를 기반으로 작성한 것이라서 불필요한 로직이 많았다. 그래서 이를 최대한 줄이고 직관적으로 구현한 코드는 아래와 같다.
import java.util.*;
import java.util.stream.*;
class Solution {
public String solution(String number, int k) {
char[] numbers = number.toCharArray();
Stack<Character> stack = new Stack<>();
// 문자를 제거한 횟수만 기억.
int count = 0;
// 문자열의 문자들을 스택에 삽입하여 동일하게 진행.
for(char n: numbers) {
if(stack.empty()) {
stack.push(n);
continue;
}
while(!stack.empty() && stack.peek() < n && count < k) {
stack.pop();
count++;
}
stack.push(n);
}
// 빼야 하는 만큼 낮은 자릿수의 숫자들을 제거.
// 스택에는 역순으로 저장되어 있으니 가능한 것.
while(count++ < k) {
stack.pop();
}
// 스택에 들어있는 문자들을 역순으로 조합하여 반환.
StringBuilder sb = new StringBuilder();
while(!stack.empty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}속도 측면에선 별 차이가 없지만 훨씬 더 간단하고 알아보기 쉬운 코드로 작성할 수 있었다.
후기
처음에는 주어지는 정수가 1부터 1,000,000 사이인 줄 알았는데 문제를 다시 읽어보니 한 자릿수부터 1,000,000 자릿수까지 주어질 수 있는 매우 큰 정수였다. 이는 일반적인 자료형으로는 다룰 수 없기 때문에 문자열을 활용하도록 풀이를 고치고 시간 초과 때문에 다른 전략을 찾아보게 된 계기가 되었다.
실제 코딩 테스트를 볼 때도 이렇게 문제를 제대로 읽지 않으면 좋은 결과를 얻기 어려울 것이다. 주의하자.
그리고 테스트 케이스도 직접 구상해보면서 실행하다보니 생각지도 못한 반례를 찾을 수 있었다. 예를 들어 "5432112345"는 "54345"가 나와야 하는데 "54325"로 나와서 로직의 결함을 알 수 있었던 좋은 경험이였다.
