개요
-
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
접근 방식
-
k개의 수를 제거했을때 가장 큰 수가 나오려면,
앞에서부터 작은 수를 제거해야한다. -
앞에서부터 작은 수를 어떻게 제거할까 고민하던 중,
간단하게 접근해봤다.
수가 제일 크게 되려면 수열이 내림차순을 형성해야한다.
따라서 수열을 앞에서부터 순회하며 오름차순이 되어있는 부분을 제거해주면 된다. -
반복문을 통해 바로 뒤의 숫자가 자신보다 크다면 해당 숫자를 제거하면 된다.
-
예전 [소수 찾기 문제 ]에서 본 풀이에서 영감을 얻어 string에서 한 글자를 빼는데
substr을 이용해 풀었다. -
숫자가 최대 100만자리다.
내 방식의 최악의 경우는 숫자가 백만자리 전부 같은 숫자로 나오거나
내림차순을 형성한 수가 나왔을 때이다.
그래서 시간이 안 될거 같았는데 제일 오래걸린 테스트케이스가 9천ms로 통과했다.
다른 코드를 찾아봐야겠다.
전체 코드
#include <string>
#include <vector>
#include<iostream>
using namespace std;
string solution(string number, int k) {
string answer = "";
while(k>0){
bool erased=false;
for(int i=0;i<number.length()-1;i++){
if(number[i]<number[i+1]){
if(i==0) number= number.substr(1,number.length());
else number=number.substr(0,i)+number.substr(i+1,number.length());
erased=true;
break;
}
}
//내부가 내림차순으로 정렬되어있다면 마지막 숫자 제거
if(!erased)
number.erase(number.length()-1);
k--;
}
return answer=number;
}생각
다른 분의 풀이
https://ssocoit.tistory.com/38
위 블로그에서 본 풀이이다.
-
기본적인 생각은 answer의 크기를 전체 사이즈 - k 만큼 미리잡는다.
이 answer의 크기만큼 숫자를 넣어주면 된다.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에 가장 큰 수를 넣는다 } -
answer사이즈만큼 반복해서 각 구간의 제일 큰값을 찾은 후, maxint에 넣어준다.
-
첫번째 for문내부로 들어가자.
각 구간의 제일 큰 값과 인덱스를 저장하기위해 maxint, maxidx변수를 선언했다.두번째 for문을 통해 구간을 정하는데, 구간은 startidx에서 k+i까지만이다.
k+i가 전체 사이즈이다.이 부분이 의미하는 바는 첫번째 반복문에서 인덱스 i가 0부터 전체사이즈 -k 만큼 돈다고
비교도 인덱스 0부터 전체사이즈 -k만큼만 둘 순 없다.왜? i는 answer에 각 구간의 제일큰 숫자를 answer-k개만큼 넣어주기 위해 answer-k만큼 돌지만,
각 자리의 숫자를 비교할때는 모든 숫자를 다 비교해야하기 때문이다.전체를 다 봐야하므로 i에 k를 더해서 startidx부터 k+i까지의 구간을 비교하면서 전체 범위를 다 보게 된다.
또 각 비교구간 범위가 i+k까지 설정하는것만으로도 제거해야하는 갯수가 제어가 된다.
max값을 찾은 후에는 startidx를 max값인덱스+1로 넣어주고 answer에 해당 max값을 넣어준다.
max 이전값들은 어차피 각구간의 최대값만 넣어주는 코드 특성상 불필요한 값이다.
코드
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;
}
출처 : https://ssocoit.tistory.com/38 [코딩하는 경제학도]
Copyright © SsocoIT