[프로그래머스 C++] 큰 수 만들기

 

[프로그래머스 C++] 큰 수 만들기

 

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

프로그래머스

---

 

해결전략

 

탐욕법, 그리디 알고리즘, Greedy Algorithm

 

---

 

 

처음 시도한 코드 - 시간초과

 

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

vector<string> dp;

string solution(string number, int k) {

    int n = number.size();
    int t = n - k;
    dp.resize(n);

	for(int i=0; i<t; i++){
        dp[t - 1] += number[i];
	}

    for(int i = t; i < n; i++)
    {
        dp[i] = dp[i - 1] + number[i];

        int j = 1;
        while(true)
        {
            if (dp[i][j - 1] < dp[i][j]) {
                dp[i].erase(j - 1, 1);
                break;
            }

        	j++;
        }
        // 맨 마지막 숫자가 가장 작은 경우, 숫자가 안 빠졌으므로 마지막 숫자 빼기
        if (dp[i].size() > t) {
            dp[i].erase(j, 1);
            break;
        }
    }
        
    return dp[n-1];
}

 

---

 

정답 코드

 

#include <string>
using namespace std;

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

    int n = number.size();
    int remain = n - k; // 남아야하는 숫자 개수

    int start = 0;  // 탐색을 시작할 인덱스

    for (int i = 0; i < remain; i++)  // 남아야 하는 숫자의 개수만큼 반복
    {
        char maxNum = number[start];
        int maxIdx = start;

        // start부터 k+i까지 반복하며 최대 숫자와 그 인덱스 찾기
        // 현재 숫자를 포함해서 앞으로 k개의 숫자를 제거할 수 있으므로, 현재부터 k개 뒤까지의 숫자 중 가장 큰 숫자를 선택하면 항상 최적의 해를 구할 수 있기 때문이다.
        for (int j = start; j <= k + i; j++) 
        {
            if (maxNum < number[j]) {
                maxNum = number[j];
                maxIdx = j;         // 찾은 최대 숫자의 위치는 maxIdx에 저장
            }
        }

        start = maxIdx + 1; // start를 최대 숫자의 다음 인덱스로 갱신

        answer += maxNum;  // 최대 숫자를 결과 문자열에 추가
    }

    return answer;
}

 

 

 

 

---

 

다른 풀이

 

#include <string>
#include <deque>
using namespace std;

string solution(string number, int k) {
    deque<char> dq;

    for (int i = 0; i < number.size(); i++)  // number의 각 숫자를 차례대로 검사
    {
        // 덱이 비어있지 않고, 덱의 가장 뒤에 있는 숫자가 현재 숫자보다 작고, 아직 k개 이상의 숫자를 제거할 수 있는 경우에 반복
        while (!dq.empty() && dq.back() < number[i] && k > 0) 
        {
            dq.pop_back(); // 덱의 가장 뒤에 있는 숫자를 제거
            k--; 			// 제거할 숫자의 개수를 줄인다
        }
        dq.push_back(number[i]); // 현재 숫자를 덱의 뒤에 추가
    }

    
    while (k--) { // 아직 k개의 숫자를 더 제거해야 하는 경우, 덱의 뒤에서부터 숫자를 제거
        dq.pop_back();
    }

    string answer = "";
    while (!dq.empty()) // 덱이 빌 때까지 반복
    {
        answer += dq.front(); // 덱의 가장 앞에 있는 숫자를 결과 문자열에 추가
        dq.pop_front(); // 덱의 가장 앞에 있는 숫자를 제거
    }

    return answer; 
}