문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
| number | K | return |
| "1924" | 2 | "94" |
| "1231234" | 3 | "3234" |
| "4177252841" | 4 | "775841" |
문제 해설
가장 큰 수의 조건을 생각하자.
가장 큰 수는 모든 객체를 뺐을 때, 좌측값이 가장 커야함을 기억해야 한다.
number는 2자리 이상, 1,000,000자리 이하인 숫자 라는 것은, int나 double같은 데이터형 숫자가 아닌, string형태의 데이터 임을 기억하자.
백만자리 수 까지 계산해야한다는 뜻 이다. 숫자의 최대값이 9,999,999가 아니라, string의 길이가 최대 1,000,000까지 있다는 뜻이다.
이해하기 쉽게 쓴다면,
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
가 아니라
- number는 2자리 이상, 1,000,000자리 이하인 문자열입니다.
라고 써야 맞다. 이 프로그래머 공과생들 국어교육좀 다시해야한다.
첫 시도
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
string answerstring;
void insertnum(string number, int k, int target ,int nownum = 0)
{
int count = nownum + 1;
if(count > k)
return;
for(int i = 0; i < number.size(); i++) {
string newnumber = number;
newnumber.erase(i, 1);
if(newnumber.size() == target) {
if(stoi(answerstring) < stoi(newnumber))
answerstring = newnumber;
}
insertnum(newnumber, k, target, count);
}
}
string solution(string number, int k) {
answerstring = "0";
insertnum(number, k, number.size() - k);
return answerstring;
}실패
모든 테스트는 다 통과하나, 좀더 효율적으로 짜라고 빠꾸먹인 느낌이다.
그냥, 모든 객체를 다 돌려보면서, 내가 원하는 사이즈가 나왔을 때 전체비교연산을 통해 비교를 하고, 큰 숫자일 경우에만 대입되도록 바꾸었는데. 실행은 되나 효율적이지 않은느낌?
두 번째 시도
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
set<string> answerstring;
void insertnum(string number, int k, int target ,int nownum = 0)
{
int count = nownum + 1;
if(count > k)
return;
for(int i = 0; i < number.size(); i++) {
string newnumber = number;
newnumber.erase(i, 1);
if(newnumber.size() == target)
answerstring.insert(newnumber);
insertnum(newnumber, k, target, count);
}
}
string solution(string number, int k) {
insertnum(number, k, number.size() - k);
return *answerstring.rbegin();
}실패
효율문제가 아니라 문항 제한조건이 이상하게 써져있었다.
제한조건에서 2이상 1,000,000자리 숫자가, 최대값이 7자리가 아니라 최대값이 백만자리의 숫자라는 의미였음.
그래서 고쳤는데, 시간초과로 실패
세 번째 시도
#include <string>
#include <vector>
using namespace std;
string solution(string number, int k) {
string answer = number;
while(k > 0) {
int nowsize = answer.size();
for(int i = 0; i < answer.size(); i++)
{
if(answer[i] < answer[i+1]) {
answer.erase(i, 1);
k--;
i--;
break;
}
if(k <= 0)
break;
}
if(nowsize == answer.size()) {
answer.erase(answer.size() - 1, 1);
k--;
}
}
return answer;
}성공
개념자체를 바꿔봤음,
데이터를 전부 넣는것 이 아니라, 조건을 생각해서
가장 왼쪽에 있는 값이 가장 작으면 안된다. 라고 생각. 이걸 뒤집으면 나보다 오른쪽값이 크다면, 나 자신을 빼버리면 됨.
빼버린 다음에 for문 회전에서 한개가 줄었음으로 i를 한개 빼주고, 한개를 뺐음으로 k를 한개 빼줌.
그렇게 해서, for문을 처음부터 다시 돌릴 수 있게 함.
만약, 한개도 빼지 못헀다면, 왼쪽의 모든값은 오른쪽 값보다 크다는 의미 임으로, 가장 작은값은 가장 우측의 값임을 알 수 있음.
이 예외처리를, size로 확인하고, 해당 size와 시작size가 같다면, 하나도 못뺐다는 의미 임으로, 맨 뒤 값을 한개 빼주면됨.
