[프로그래머스] 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;
}

 

 

실행 결과