프로그래머스 - 큰 수 만들기

문제 설명

 

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

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

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

 

제한 조건

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

문제 설명과 제한 조건은 위와 같다.

 

입출력 예는 이렇다.

 

처음에는 배열을 이용해서 풀어보려고 했다.

시도한 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(string number, int k) {
   	string answer = "";
	int result = 0;
	int temp = 0;
	for (int i = 0;i < number.size();i++) {
		string cp = "";
		cp += number;
		int count = 0;
		for (int j = i; j < cp.size(); j++) {
			count++;
			cp.erase(find(cp.begin(), cp.end(), cp[j]));
//아마 이런식으로 작업하면 계속 index 참조 오류가 발생했을거임.
			if (count == k) {
				result = max(result, stoi(cp));
				break;
			}
		}
		
	}
	answer = to_string(result);
	return answer;
}

아마 그냥 손가는대로 작성한 코드라 완성되지도 않았을 코드지만 실행하면 첫번째 케이스만 통과했었다.

예상되는 문제점은 j 인덱스와 cp가 erase 되면서 인덱스 참조 오류가 발생했을거라고 추측하고 있다.

 

그래서 한참을 고민하다가 인터넷에 검색해서 아이디어를 얻었다.

스택을 이용한 풀이 방법이였다.

 

스택을 이용해서 풀면 편한 이유는 숫자를 k 만큼 지워서 만들어진 숫자들 중에서 가장 큰 값을 찾는 문제이므로

자릿수를 이루는 각 숫자가 순서를 지켜서 만들어져야 하기 때문인거 같다.

 

즉 숫자의 순서가 중요하지 않은 조합이 아닌 숫자가 들어오는 순서가 중요하기 때문이다.  

 

풀이 코드는 아래와 같다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
stack <int> s;

string solution(string number, int k) {
   	string answer = "";
    char cur=0;
    char top=0;
    int size = number.size() -k;
    for(int i=0;i<number.size();i++){
        cur = number.at(i);
        while(!s.empty() && k>0){
            top = s.top();
            if(cur > top){
                s.pop();
                k--;
            }
            else break;
        }
        s.push(cur);
    }
    while(s.size() != size) s.pop();
    
    while(!s.empty()){
        answer += s.top();
        s.pop();
    }
    reverse(answer.begin() , answer.end());
    
	return answer;
}

 

코드에 대한 설명을 하자면 

들어온 string number 의 길이만 큼 for문을 돈다.

그리고 현재 인덱스의 값을 cur 변수에 담아주는데  그 뒤로 while 문을 돌면서

스택에 있는 top의 값과 계속 비교를 해준다. 물론 k 번 만큼만 숫자를 지울 수 있기 때문에 그 조건도 포함한다.

그리고 for문의 마지막엔 값을 스택에 넣어준다.

 

이 동작을 반복하면 스택의 top 과 현재 비교하고자 하는 값중

현재값이 더 크면 스택에 있던 그 보다 작은 값들은 모두 나오고 

이 나오는 부분이 바로 숫자를 제거하는 동작이 된다. 그러므로 그만큼 k-- 를 한다.

 

큰 값이 숫자의 앞자리수가 되게 되면서 자연스레 가장 큰 값이 만들어지게 된다.

마지막에는 스택이므로 최근에 쌓인 숫자부터 출력되기 때문에

reverse 를 이용해서 거꾸로 문자열을 만들어준다.

 

예를 들어서 보면

 

"4177252841" 라는 숫자가 있고 k가  4라고 가정하자

 

먼저 4가 스택에 들어간다.

그다음 cur 은 1이 된다. 

스택의 top 은 4다

4와 1을 비교한다.

top인 4가 더 크므로 그냥 스택에 쌓인다.

 

스택에는 4, 1 이 들어있다.

다음 7이 cur가 된다.

스택의 top인 1과 비교한다. 

cur 인 7 이 더 크므로 스택을 pop하고 

k-- 를 한다.

그다음 스택의 top은 4 가 되고

이것도 cur 의 7 보다 작으므로 pop 되고 k--를 한다.

 

이렇게 반복하면

 

답은 775841 가 만들어진다.