고득점 KIT의 그리디 문제 6개 중 세 번째 문제인 큰 수 만들기를 풀어봤습니다.
아이디어를 생각하기 굉장히 까다로운 문제였습니다.
처음에 완전 잘못 생각해서 2~3시간을 날렸습니다.. 분명 맞는 것 같은데 통과를 못해서.. 눈물을 머금고 아예 갈아 엎었습니다.
그렇다면 바로 문제 해설로 넘어가시죠!
출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/42883
코딩테스트 연습 - 큰 수 만들기
programmers.co.kr
목차
0. 문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
0.0. 제한 조건
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
0.1. 입출력 예
| number | k | return |
| 1924 | 2 | 94 |
| 1231234 | 3 | 3234 |
| 4177252841 | 4 | 775841 |
1. 풀이 과정
매우 친절하게 주석에 한줄 한줄 달아놓았기 때문에 간략하게 설명하..면 안되겠죠?
알고리즘 자체는 크게 어렵지 않지만, 처음에 떠올리는 것이 굉장히 어려웠습니다.
먼저 string 형태의 answer의 크기는 number.size() - k입니다.
이걸 이용해서, for문을 number.size()-k만큼 돌린 후에 한번에 한글자씩 answer에 넣으면 무언가 될 것 같다는 생각이 들기 시작합니다. 이 부분이 중요합니다.
이 for문 안에서는 한 번 돌 때마다 특정 범위만큼을 검색해야합니다. 정답 글자수가 number.size()-k로 정해져있기 때문에 answer을 완성시키기 위해서는 뒤에 최소한의 값들을 남겨놓아야 합니다. 그래서 index가 k+i인 number값까지만 확인합니다. 기본적으로 뒤에 k-1개 만큼의 수를 남기고, 추가적으로 앞에서 이미 answer에 넣은 값이 존재하므로 그 값의 수만큼은 남길 필요가 없습니다. 그리고 이 값은 for문이 돌아간 횟수, 즉 i와 일치합니다. 따라서 k+i까지 조사합니다. (등호가 들어갑니다. 만약 k가 2고 number이 4자리라고 할 때 정답은 2자리가 나와야하는데, 뒤에 1개만 남기는 경우 0,1,2의 index를 조사해야하죠? 등호가 필요한 이유를 직관적으로 볼 수 있는 케이스가 되겠습니다!)
그리고 for문 안 for문에서 maxint와 maxidx를 구해줍니다.
이 작업을 완료해서 최댓값과 최댓값의 index를 구했다면, 최댓값을 answer에 넣고, startidx를 최댓값의 index의 다음 index로 넣어줍니다. 이 과정을 통해 다음 바깥for문을 돌릴 때 안쪽 for문에서 최댓값 다음 수부터 조사하게 됩니다.
ex) number = "15243", 3 이면 정답 글자수는 number.size()-k인 2가 되고, 첫 번째는 1,5,2,4를 조사합니다.(이 중에 1개가 선택되고, 앞으로 최소 1개 더 골라야 하므로 뒤에 1개의 수를 남겨야합니다) 5가 가장 큰 수이므로 answer에 5를 넣습니다. 그 다음엔 5 다음에 위치한 2부터 순서대로 2,4,3을 조사합니다.(k는 3이고, i는 1이므로 index가 4인 3까지 전부 조사합니다.) 이 중에서 4가 가장 큰 수이므로 4를 answer에 넣습니다. for문이 끝나고 answer값인 "54"를 반환합니다.
2. 소스 코드
2.0. 정답 코드
#include <string>
#include <vector>
using namespace std;
string solution(string number, int k) {
string answer = "";
// answersize만큼 for문을 돌려서 한 번에 한 글자씩 answer를 따오고, 한 번 돌릴 때마다 startidx부터 k+i까지 돌린다.
// 이렇게 한도를 두고 돌려야 answersize만큼의 answer 글자들을 뽑아올 수 있기 때문이다.
int answersize = number.size() - k; // return값의 길이는 number의 사이즈에서 k를 뺀 것
int startidx = 0; // 시작 index
for(int i = 0; i < answersize; ++i){ // answersize만큼 반복
char maxint = number[startidx]; // 처음에는 startidx의 값이 최대값
int maxidx = startidx; // 처음에는 maxidx가 startidx
for(int j = startidx; j <= k+i; j++){ // startidx부터 k+i까지 확인해서 max값 찾음 -k
if(maxint < number[j]){ // 더 큰 값이 나오면 그 값의 index와 number를 저장
maxint = number[j];
maxidx = j;
}
}
startidx = maxidx + 1; // 다음번에는 maxindex + 1에서부터 시작
answer += maxint; // answer에 가장 큰 수를 넣는다
}
return answer;
}
2.1. 시행착오를 겪은 틀린 코드
#include <string>
#include <vector>
using namespace std;
string solution(string number, int k) {
string answer = "";
// 2개의 수를 비교해서 앞 수가 더 크면 answer에 넣고, 뒷 수가 더 크면 앞 수를 버린다. 만약 다 빼지 못한 상황에서 끝까지 다 돌았다면 처음부터 다시 돈다.
// 지워야 하는 수의 남은 수를 k에서 빼나감
int idx = 0;
while(1){
for(int i = 0; i < number.size(); ++i){
if(number[i] >= number[i+1]){
answer += number[i];
}
else
--k;
if(k == 0 && i != number.size()-1){
for(int j = i+1; j < number.size(); ++j){
answer += number[j];
}
return answer;
}
else if(k == 0 && i == number.size()-1)
return answer;
}
number = answer;
answer = "";
}
return answer;
}
그리디라고 해서 앞 두 수를 비교하는 방법을 생각했는데, 위 테스트5 예시를 통과하지 못해서(무한루프에 걸려서 시간초과가 납니다) 전부 갈아엎게됩니다. 저같이 실수하지 마시라고 올려봅니다.. ㅋㅋㅋㅋ
3. 후기
잘못된 알고리즘을 시도했을 때 얼마나 시간을 버릴 수 있는가(...)를 적나라하게 알 수 있었던 그런 문제였습니다.
집에서 푼 문제가 아니다보니 종이에 알고리즘을 생각하기보다 서둘러 코드를 짜는 데 몰두한 것이 원인이 아닐까 싶습니다. 알고리즘 문제를 풀 때는 어떤 방식으로 해야 문제가 해결되는 지 정확하게 파악하는 것이 코드를 구현하는 것보다 훨씬 중요하다는 것을 깨닫게 된 좋은 시간이었습니다! 내 24시간 ㅠ
최근댓글