문제 이해 단계
숫자로 이루어진 문자열이 주어지고, 그중에서 없애야 할 문자의 수 k가 주어진다.
k개를 지워서 문자열 중 가장 큰 숫자를 만드는 것이다.
여기서 중요한 점은 무조건 k개를 다 써야 한다는 것이다.
문제 접근 단계
상식적으로 한번 접근해 보자. 어떤 문자열(숫자배열)일수록 크다고 할 수 있을까?
당연히 기본적으로 다른 숫자들보다 자릿수가 많으면 비교할 필요도 없이 더 큰 숫자일 것이다.
예를 들어 두 자릿수의 최솟값 (10)은, 한 자릿수의 최댓값(9)보다 무조건 큰 것처럼 말이다.
그럼 비교하는 두 숫자의 자릿수가 같다면?
가장 높은 10의 자리(숫자 배열의 첫 인덱스)가 높은 숫자가 큰 것이다.
예를 들어, "399"와 "400"을 비교하면,
가장 높은 자릿수인 '3'과 '4'만 보고 "400"이 더 큰 수 있은 것을 알 수 있듯이 말이다.
여기서 당연히 두 숫자배열의 첫 인덱스가 같다면,
그다음으로 큰 두 번째 인덱스를 비교하며 된다.
위의 로직을 요약해 보면 이렇게 된다.
위의 로직을 해당 문제에 응용해서 풀어보도록 하자.
문제에서는 k개를 삭제해서 최댓값을 만들어야 한다.
그리고 무조건 k개를 삭제해야 하기 때문에 만들어지는 숫자열의 길이는 전부 일정하다.
정답 숫자열의 길이는 입력 문자열에 k개를 삭제한 것만큼의 길이이다.
정답 숫자열의 길이 = (입력 문자열) - k
여기서 중요한 점은 위의 로직에서 숫자열의 길이를 비교해서
크기를 비교하는 것은 할 수 없게 됐다는 것이다.
왜냐하면 어차피 나오는 출력의 길이는 똑같으니까.
그래서 두 번째 조건인 "가장 높은 자리의 숫자를 비교해서 더 높은 게 크다"라는 방식을 이용해야 한다.
즉, 가장 큰 숫자열을 만들어줘야 하기 때문에 앞자리일수록 큰 숫자가 오게 해야 한다.
세 번째 입력인 "4177252841", k = 4로 예시를 들어보자.
일단 가장 높은 자릿수부터 가능한 크게 만들어보자.
k = 4이기 때문에 최대한으로 숫자열을 제거했을 때, 맨 앞에 올 수 있는 숫자후보는?
k = 0 일 때, 4
k = 1 일 때, 1
k = 2 일 때, 7
k = 3 일 때, 7
k = 4 일 때, 2
이렇게 총 5가지다.
당연히 이 중에서 이 숫자를 가장 크게 만들기 위해서는 앞에 7이 와야 한다.
k를 최대한 적게 쓰면서(삭제 기회는 아끼는 것이 이득이기 때문)
숫자를 제일 크게 하는 것은 k = 2 일 때 그러니까, 4와 1을 삭제하는 것이다.
4와 1을 삭제한 상태는 "77252841"이다.
가장 높은 자릿수를 가능한 숫자들 중 제일 높은 걸로 고정해 줬다.
여기서 한 번 더 이 숫자열이 가장 큰 숫자열이 되도록 하고자 한다면?
바로 그다음 높은 자릿수를 크게 만드는 것이다.
"77252841"
삭제를 2번 했으므로 남은 삭제 기회는 2번 ( k = 2 )이다.
그러므로 가능한 후보는
k = 0 일 때, 7
k = 1 일 때, 2
k = 2 일 때, 5
이 중 가장 큰 수는 k = 0 일 때 7이다.
같은 논리로 계속 반복해 보면
"77252841" (남은 삭제 기회 : 2)
에서 k = 1일 때 5가 최댓값
"7752841" (남은 삭제 기회 : 1)
에서 k = 1 일 때 8이 최대 값
"775841" (남은 삭제 기회 : 0)
즉 답은 "775841"이 된다.
전체적인 로직은 위와 같다. 알고리즘을 요약하자면,
1. 숫자 배열 인덱스 0번부터 k+1 중 가장 큰 숫자의 인덱스를 가져온다.
2. 그 인덱스만큼 이동하고 그 앞에 있던 것들은 삭제한다.
3. 삭제한 만큼 k에서 뺀다.
4. 정해진 자릿수 다음 자릿수에서 1~3 과정을 k가 0일 때까지 반복한다.
로직은 위가 끝이지만, 사실문제 구현 과정에서 예외처리나 생각해야 할 부분이 많았다.
이 부분에 대해서는 문제 구현 단계에서 코드를 설명하면서 이야기하겠다.
문제 구현 단계
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string solution(string number, int k) {
string answer = "";
int cnt = 0; // 현재 확인할 문자 인덱스
int count = k; // count에 전체 K개의 수 저장
int idx = 0; // 최대값의 인덱스
// K개를 다 제거했거나, 정답 문자열의 개수가 나와야되는 개수보다 초과되거나, number 배열을 넘거나
while(k > 0 && answer.length() < number.length() - count
&& cnt < number.length())
{
int maxVal = 0;
// 현재 확인할 인덱스 ~ k까지 숫자 중 가장 큰 인덱스를 찾는다.
for(int i = cnt; i < cnt+k+1 && i < number.length(); i++){
if(number[i] > maxVal){
idx = i;
maxVal = number[i];
}
}
// 해당 문자를 정답 배열에 넣음
answer.push_back(number[idx]);
// 시작한 인덱스(cnt) ~ 최대값까지 온 거리(idx)만큼 문자 삭제
k -= (idx - cnt);
// 최대값의 다음 인덱스부터 확인하게 함
cnt = idx+1;
}
// 아직 삭제 기회가 남아있다면 이미 정답 개수를 다 채운 상태이기 때문에 버려야함
// 현재 인덱스에서 k만큼 이동하여 버림
if(k > 0) cnt = cnt+k;
// cnt가 다 이동하지 않았을때를 대비해서 number 끝까지 이동시킴
for(int i = cnt; i < number.size(); i++) answer.push_back(number[i]);
return answer;
}정답을 구하는 방식은 문자열 인덱스를 cnt라는 기준점을 두고
특정 문자만 answer 문자열에 담는 방식으로 하였다.
여기서 while(answer.length() < number.length() - count)라는 조건은
"9999", k = 2 같은 입력이 들어왔을 때를 대비한 것이다.
저 처리 없이 위와 같은 입력이 들어오면,
해당 알고리즘에서는 최댓값이 9이므로 "9999"가 나올 수 있기 때문에
나와야 하는 정답의 자릿수보다 더 길게 나와버린다.
while문을 탈출하고 밑에 보면 if(k > 0) cnt = cnt+k;가 있는데
이는 남은 삭제 기회를 소비시키기 위해서이다.
예를 들어 "1991", k = 2이 들어오면,
99가 완성된 상태에서 이미 길이가 number.length()-k = 2와 같아 while문을 탈출한다.
위 코드가 없다면 현재 남은 문자부터 문자열의 끝까지 정답에 넣는 코드 때문에 "991"이 돼버릴 것이다.
그래서 k만큼 삭제(인덱스 이동) 해준다.
밑에 number를 끝까지 이동시키는 걸 쓰는 이유는,"1999", k = 1인 경우, 1을 삭제하고,
answer에는 9가 들어가고, while문을 탈출한다.
그래서 남은 부분(cnt = 인덱스 2)부터 끝까지 다 넣어주는 것이다.
시행착오
정말 정말 너무너무 오래 걸렸다.
로직을 생각하는 데는 오래 걸리지 않았다. 하지만 구현에 많은 시간을 썼다.
다시 한번 구현에 약함을 깨달았다.
구현을 위주로 공부해야겠다. 나는 구현이 문제다.
또한 테스트케이스를 통과하지 못해서 엄청나게 고생했는데 여기서 한 3시간은 쓴 것 같다.
마지막에는 어이없게 풀리긴 했는데,
여기서 왜 char형을 int형으로 바꾸는 방법인 'a' - '0'이 안될까?
이거에서 '0'을 지우니까 바로 정답이 뜨더라.
예외처리를 구현하는 데에 애먹었고,
디테일한 부분을 살리는 것이 정말 어려웠다.
나는 항상 예외처리가 문제인 것 같다.