프로그래머스[Lv.2] - 큰수

.

 

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

---

 

 

 

 

 

 

제한 사항

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

 

 

 

 

 

 

풀이

간단해 보이지만 쉬운 문제는 아니다. 

처음에는 문제를 잘못 이해해 정렬하여 가장 작은 수를 k개 제거하였다.

하지만, 이 문제는 순서를 변경하지 않고 k개를 제거해 큰 수를 만드는 문제였다.

 

한가지 생각해 낸 정보는 현재 처리하는 수가 다음 수 보다 작다면 그 수는 제거되어야 한다는 것이다.

따라서, 앞에서부터 하나씩 집어 넣으며 뒤의 수보다 작다면 제거하는 것이다.

이때, 집어 넣는 수만 제거하는 것이 아니라 그전에 집어넣은 수 모두 제거해야 한다.

이 과정에서 k개를 제거했다면 반복을 종료한 뒤 남은 수들을 추가하면 된다.

만약, 모든 수를 집어 넣었는데 k개를 제거하지 못했을 경우가 생긴다.

예를 들면, 99991 같은 경우 모두 동일한 수가 있어 제거하지 않으며, 마지막 수는 뒤의 수가 없어 비교하지 않아 제거하지 못한다.

이러한 경우가 k개를 제거하지 못한 경우이다.

그렇다면 저 중 일부분은 규칙에 맞게 제거되어 저장한 배열에 있을 것이다.

이 배열에서 앞에서부터 k개를 제거한 개수를 선택해 주면 된다.

즉, 문자열의 길이가 10이었고 k가 3이었다면 앞에서부터 7개를 선택하면 된다.

 

위와 같은 과정의 편의를 위해 자료구조 몇 개를 사용한다.

수를 선택하여 집어넣는 배열은 최근에 넣은 순서대로 비교하여 제거할 가능성이 있다.

따라서, stack을 사용한다. (c++: vector)

또한, 기본 문자열을 변환하여 저장한 뒤 앞에서부터 선택해야 하는 배열이 있다.

즉, 원본 배열은 앞에서 부터 비교해야 하기 때문에 queue를 사용한다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    int temp = number.size() - k;
    
    queue<int> num;
    vector<int> result;
    for(auto c : number)
    {
        num.push(c-'0');
    }
    
    while(!num.empty() && k > 0)
    {
        result.push_back(num.front());
        num.pop();
        
        while(!result.empty() && result.back() < num.front() && k>0) {
            result.pop_back();
            k--;
        }
    }
    
    while(!num.empty())
    {
        result.push_back(num.front());
        num.pop();
    }

    
    for(int i = 0; i < temp; i++)
    {
        int n = result[i];
        answer += n+'0';
    }
    

    
    return answer;
}

---