I 문제 소개
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
II 문제 풀이
문제가 상당히 쉬워보인다. 그렇지만 이것은 정말 크나큰 오해였다.
숫자로 이루어진 문자열에서 k개의 원소를 제거하되 가장 큰 수를 만들어야한다.
가장 큰 수를 만들기 위해서는 이 수를 버릴지 말지 고민할 때마다 최선의 선택을 하다보면 만들어질 것 같았다.
즉, 탐욕법(Greedy Algorithm)과 관련된 문제다!
그럼 최선의 선택이 무엇인지를 생각해보아야 하는데, 다음과 같이 생각해보았다.
문자열의 크기가 11이고, k=4라면 answer의 형태는 _ _ _ _ _ _ _(일곱 자리)이다.
그렇다면 일곱 자리 중 맨 앞자리를 정하는 것은, 나머지 여섯자리는 문자열 끝에 있는 여섯개의 수로 배정한다고 치고 그 여섯개를 제외한 앞에서부터 다섯개의 수에서 가장 큰 수가 될 것이다.
말로 표현하려니까 복잡해졌는데, 예시를 들어보겠다.
number = "41772528421"(11자리) / k = 4일 때
0) answer = _ _ _ _ _ _ _
1) answer = (41772 中 가장 큰 수) _ _ _ _ _ _ = 7 _ _ _ _ _ _
2) answer = 7 (725 中 가장 큰 수) _ _ _ _ _ = 7 7 _ _ _ _ _
3) answer = 7 7 (252 中 가장 큰 수) _ _ _ _ = 7 7 5 _ _ _ _
4) answer = 7 7 5 (28 中 가장 큰 수) _ _ _ = 7 7 5 8 _ _ _
5) answer = 7 7 5 8 4 2 1 // 이미 4개가 없어져서 더이상 제거하지 않아도 일곱 자리를 충족함
이제 이걸 코드로 옮기면 되겠다.
문제가 큰 수 찾을 때 스택 쓰기 좋아보여서 스택을 쓰기로 했다.
0. 초기 환경 설정
#include <string>
#include <stack>
using namespace std;
string solution(string number, int k)
{
string answer = "";
stack<char> sNum;
int i,j;
int ibeg, iend, temp;
return answer;
}char형 스택 sNum을 만들었다. 굳이 int로 만들지 않은 이유는 복잡한 연산이 들어가지 않고 크기 비교만 할 것이기 때문이다.
ibeg와 iend는 숫자를 비교할 때 쓸 범위를 지정해줄 변수다.
1. 계산, 근데 이제 스택을 곁들인
j = k;
ibeg = 0;
iend = k+1;
while (1)
{
/* 수 비교 */
for (i = ibeg;i < iend;i++)
{
if (i == ibeg) {
sNum.push(number[i]);
temp = i;
}
else if (sNum.top() < number[i] && j > 0)
{
sNum.pop();
sNum.push(number[i]);
temp = i;
}
}
/* 변수 제어 */
j -= temp - ibeg;
ibeg = temp+1;
if(iend <= number.size())
iend += 1;
/* 탈출 조건 */
if (j == 0)
{
for (i = ibeg;i < number.size();i++)
sNum.push(number[i]);
break;
}
if (ibeg == number.size())
{
if (j > 0)
for (i = 0;i < j;i++)
sNum.pop();
break;
}
}이게 계산의 전부다.
코드가 너무 복잡해 나눠서 설명하겠다.
1-1. 수 비교
for (i = ibeg;i < iend;i++)
{
if (i == ibeg)
{
sNum.push(number[i]);
temp = i;
}
else if (sNum.top() < number[i] && j > 0)
{
sNum.pop();
sNum.push(number[i]);
temp = i;
}
}j는 매개변수인 k를 직접 조정하기는 리스크가 커서 만든 변수다.
이 수 비교는 범위 내에서 push와 pop을 통해 가장 큰 수를 골라낸다.
범위를 산정하는 ibeg와 iend의 초기값 기준은,
ibeg의 경우 처음부터 비교할거니까 0으로 시작하고
iend는 "전체 길이 - (전체 길이 - 1 - 빼야하는 길이) = 빼야하는 길이(k) + 1"의 과정을 통해 산출되었다. 1의 의미는 number[number.size()]는 존재하지 않고 number[number.size()-1]까지만 존재하기 때문에 조정하기 위한 것이다.
이 수 비교 한 번을 통해 한 자리가 결정된다. 따라서 이만큼을 계속 반복해줄 것이다.
1-2. 변수 조절
j -= temp - ibeg;
ibeg = temp+1;
if(iend <= number.size())
iend += 1;1-1에서 스택에 push할 때마다 temp의 값에 그 때 index를 저장해줬다. 그 이유는 1-1이 끝난 후 다음 자리수를 결정할 때에는 push한 수 뒤부터 시작해야하기 때문이다.
j는 처음에 k로 시작했고, 건너뛴 수만큼 빼줄 것이기 때문에 temp에서 ibeg를 빼주었다.
iend의 경우 number.size()를 초과하면 안되므로 if문으로 제어했다. 등호의 유무는 (그냥 코드짜면서 대입하다가 범위 안맞아서 넣은 것이긴 한데) 아마 1-1에서 말했다시피 number[number.size()]는 존재하지 않으며, for문 조건부에서 등호가 안들어가기 떄문일 것이라고 추측해본다.
1-3. 반복문 탈출
if (j == 0)
{
for (i = ibeg;i < number.size();i++)
sNum.push(number[i]);
break;
}
if (ibeg == number.size())
{
if (j > 0)
for (i = 0;i < j;i++)
sNum.pop();
break;
}앞에서 말했다시피 우리는 1-1의 과정을 반복해가면서 자리수를 채울 것이다.
for문 같은 반복문으로 반복을 돌리기에는 조건을 생각하기가 까다로워 while문을 쓰기로 했고, 1-2에서 변수를 제어했다. 그리고 무한 루프로 만든 후 탈출하는 부분을 따로 만들기로 했다. 그 이유는 반복을 탈출하는 조건이 두가지이기 때문이다.
1) k만큼 수를 이미 다 빼버렸다.
2) 수가 내림차순이라서 건너뛸 수가 없었고, 순서대로 하나씩 push하다보니 끝에 도달했다.
1의 경우 남은 수를 다 push해버리면 끝나고,
2의 경우 뒤에 있을수록 수가 작다는 뜻이므로 남은 j만큼 pop해버리면 끝난다.
2. 스택을 문자열로 변환
answer.resize(sNum.size());
for (i = sNum.size()-1;i >= 0;i--)
{
answer[i] = sNum.top();
sNum.pop();
}1에서 모두 계산이 끝났으므로 스택을 answer로 바꿔주기만 하면 된다.
vector가 아닌 string이므로 .resize를 통해 크기를 바꾸어줬다.
스택의 자료구조는 선입후출(FILO; First In Last Out)의 특징을 가지므로 하나씩 빼서 그대로 저장하면 거꾸로 저장된다.
따라서 for문을 거꾸로 돌리면 의도한대로 저장할 수 있다.
3. 최종
#include <string>
#include <stack>
using namespace std;
string solution(string number, int k)
{
string answer = "";
stack<char> sNum;
int i,j;
int ibeg, iend, temp;
j = k;
ibeg = 0;
iend = k+1;
while (1)
{
for (i = ibeg;i < iend;i++)
{
if (i == ibeg) {
sNum.push(number[i]);
temp = i;
}
else if (sNum.top() < number[i] && j > 0)
{
sNum.pop();
sNum.push(number[i]);
temp = i;
}
}
j -= temp - ibeg;
ibeg = temp+1;
if(iend <= number.size())
iend += 1;
if (j == 0)
{
for (i = ibeg;i < number.size();i++)
sNum.push(number[i]);
break;
}
if (ibeg == number.size())
{
if (j > 0)
for (i = 0;i < j;i++)
sNum.pop();
break;
}
}
answer.resize(sNum.size());
for (i = sNum.size()-1;i >= 0;i--)
{
answer[i] = sNum.top();
sNum.pop();
}
return answer;
}최종 코드다. 계산이 복잡했지만 계산 이후에 answer로 옮기는 건 간단하게 할 수 있었다.
III 느낀점
다 맞긴 했는데 테스트 10에서 굉장히 간당간당했다.
문제에서 number가 100만자리 이하라고 했으니 아마 100만자리쯤 되는 수인 것 같다.
뭔가 오래 걸리게 할 수 있을 것 같긴한데 그걸 어떻게 해결해야할 지는 감이 오지 않는다.
지금까지 탐욕법 관련 문제는 수학적으로 슥슥 풀었어서, 이 문제도 수학적으로 푸려다가 정말 오래걸렸다.
또한 이렇게 풀면서도 범위 관련해서 자꾸 1차이로 오차가 나서 조절하는 데 오래걸렸다.
다른 사람들의 후기를 보니 이틀 걸렸다는 사람도 있었다. 나도 풀다가 포기하고 다른 문제풀까라는 고민이 많이 들었다. 막상 풀고도 테스트 10이 저렇게 나온거 보니 뭔가 찝찝하다.
알고리즘 공부를 좀 더 하고 풀었으면 좀 더 시간을 줄일 수 있지 않았을까?
Coding Space by MIR :
Programmers 큰 수 만들기 C++
프로그래머스 큰 수 만들기 C++
'Programmers > C++' 카테고리의 다른 글
| [Programmers] 전화번호 목록(C++) (0) | 2020.12.28 |
|---|---|
| [Programmers] 체육복(C++) (0) | 2020.12.23 |
| [Programmers] 괄호 변환(C++) (0) | 2020.12.14 |
| [Programmers] 완주하지 못한 선수(C++) (0) | 2020.12.11 |
| [Programmers] 크레인 인형뽑기 게임(C++) (0) | 2020.12.09 |
