탐욕법(Greedty) > 큰 수 만들기 (Level2)

문제 설명

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

프로그래머스

 

문제 설명

어떤 숫자에서 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 <queue>

using namespace std;

string solution(string number, int k) 
{
	string answer = "";

	int count = 0;
	for (int i = 0; i < number.size() - 1; i++)
	{
		if (count >= k)
			return number;

		//앞자리 수가 뒷자리 수보다 작은 경우 삭제
		if (number[i] < number[i + 1])
		{
			number.erase(i, 1);
			count++;
			i = -1;
		}

		//남은 숫자와 지워야할 숫자가 같을때 예외처리
		if (number.size() == (k - count))
			return answer;
	}

	//남은 수가 내림차순이라 아직 다 못지운 경우
	priority_queue<int, vector<int>, greater<int>> datas; //오름차순

	for (char temp : number)
	{
		string str = "";
		str += temp;
		datas.push(stoi(str));
	}
	
	while (count < k)
	{
		for (int i = 0; i < number.size(); i++)
		{
			string str = "";
			str += number[i];

			int a = 0;
			if (datas.top() == stoi(str))
			{
				number.erase(i, 1);
				datas.pop();
				count++;
				int a = 0;
				break;
			}
		}
	}

	answer = number;

	return answer;
}

 

생각해 볼 다른사람 코드

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

string solution(string number, int k) {
    string answer = "";
    answer = number.substr(k); 
    for(int i = k-1;i >=0;i--){
        int j = 0;
        do{
            if(number[i] >= answer[j]){
                char temp = answer[j];
                answer[j] = number[i];
                number[i] = temp;
                j++;
            }else{
                break;
            }
        }while(1);
    }

    return answer;
}

 

생각해 볼 것

string 에 push_back사용할 수 있다.

다른 사람 코드는 삭제할 갯수를 기준으로 나눠 스왑형식으로 구현했다. 왜 이런 방식이 도출됬는지 생각해보자