[프로그래머스] 42883_큰 수 만들기(c++)
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
numberkreturn
| 1924 | 2 | 94 |
| 1231234 | 3 | 3234 |
| 4177252841 | 4 | 775841 |
#C++ 첫 접근
- 처음 접근은 들어온 수를 오름차순으로 정렬하고 k개의 개수만큼 삭제하면 된다고 생각함.
- 그래서 sv(sorted vector)를 선언하고 sort()를 실행함. 원소들이 오름차순으로 정렬됨.
- sv와 nv를 비교하여 일치하는 곳의 숫자를 지우는 방식으로 구현함.
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
string solution(string number, int k) {
string answer = "";
vector<char> nv, sv;
for(int i = 0; i < number.length(); i++) {
nv.push_back(number.at(i));
sv.push_back(number.at(i));
}
sort(sv.begin(), sv.end());
for(int i = 0; i < k; i++){
char dNum = sv[i];
for(int j = 0; j < nv.size(); j++){
if(dNum == nv[j]) {
nv.erase(nv.begin() + j);
break;
}
}
}
for(int i = 0; i < nv.size(); i++) answer += nv[i];
return answer;
}
실행 결과
테스트 케이스가 일부만 통과됨. 예제를 다시 살펴보고 기존에 들어온 수의 순서가 바뀌면 안된다는 것을 알게 됨.
#C++ 두 번째 접근
- number로 넘어온 데이터를 한자리(한개)씩 처리하기로 결정함.
- 그래서 현재 처리할 데이터와 기존 데이터를 비교하여 삽입, 삭제를 수행하기 위해 스택 자료구조를 사용함.
- 기존에 삽입된 원소보다 처리할 원소가 크다면 기존 원소를 삭제하고 현재 데이터를 삽입함.
- 숫자의 맨 앞자리의 숫자가 크면 클 수록 좋기 때문임.
- 이때 주의할 점은 삭제 가능한 크기를 담은 k 이상으로 삭제 연산이 일어나면 안되기 때문에 조건으로 걸어줘야 함.
- 또한, 처리할 데이터가 스택의 top에 있는 원소보다 큰 경우에 삭제를 수행하는데 반복적으로 top의 원소와 대소 비교 연산을 해야함.
- 입출력 예제 3 (4177252841) 을 보자. 처음에 스택에는 4가 삽입되고 그 뒤로 1이 push됨. 그리고 7이 들어올 때 1과 비교해서 7이 더 크기 때문에 pop이 수행됨. 데이터 하나 당 loop를 한번만 실행한다면 아래와 같은 순서로 stack 연산이 일어남.
- 이렇게 될 경우 가장 맨 앞자리의 수가 7이 아닌 4가 되기 때문에 가장 큰 수를 만든다고 할 수 없음.
| 2 push | 2 pop | 8 push | ||||||||
| 2 push | 2 pop | 5 push | 5 | 5 | 5 | |||||
| 7 push | 7 | 7 | 7 | 7 | 7 | 7 | ||||
| 1 push | 1 pop | 7 push | 7 | 7 | 7 | 7 | 7 | 7 | 7 | |
| 4 push | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
[stack 상황]
- 따라서, 비교를 수행했을 때 스택에 있는 원소를 삭제하고 계속 top에 있는 원소와 비교하여 삭제를 처리해주어야 함. 그래서 whlie문을 통해 삭제 후에도 top의 원소를 반복적으로 비교할 수 있도록 구현함.
| 2 push | 2 pop | |||||||||
| 2 push | 2 pop | 5 push | 5 | 5 | ||||||
| 1 push | 1 pop | 7 push | 7 | 7 | 7 | 7 | 7 | |||
| 4 push | 4 | 4 | 4 pop | 7 push | 7 | 7 | 7 | 7 | 7 | 7 |
[stack 상황]
- 그리고 k개만큼 삭제를 못한 경우도 있기 때문에 k개와 같아지도록 pop 연산을 수행함.
- 이것이 가능한 이유는 스택에 들어간 원소는 이전 원소보다 작거나 같다는 의미이기 때문임.
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
string solution(string number, int k) { //큰 수 만들기 - success
string answer = "";
int size = number.length() - k;
stack<char> st;
for(int i = 0; i < number.length(); i++){
char cur = number.at(i); //처리할 숫자
while(!st.empty() && k > 0){ //
char top = st.top(); //스택의 가장 맨 위의 값
if(top < cur){ //값 비교
st.pop(); //처리할 값이 더 크기 때문에 pop 수행
k--; //제거 횟수 감소
}
else break; //비교할 때 값이 같거나 스택에 있는 값이 더 큰 경우
}
st.push(cur); //처리하는 값이 큰 경우를 제외하고 모든 경우 스택에 삽입
}
//처리하고 남은 스택의 사이즈와 제거하고 남아야하는 수가 같아야함.
//아닌 경우 같아질 때까지 제거(스택에 남아있다는 것은 제거할 원소보다 이전 원소가 작거나 같다는 의미이므로)
while(st.size() != size) st.pop();
while(!st.empty()){ //결과값 생성
answer += st.top();
st.pop();
}
//위에서 거꾸로 값이 이어졌기 때문에 reverse 수행
reverse(answer.begin(), answer.end());
return answer;
}
실행 결과
