[알고리즘] 탐욕법(c++)

※ 문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/42883#

1. 문제 개요

주어진 수(string)에서 k개의 숫자를 제거한 수 중 가장 큰 수(string)를 반환하는 아주 심플해보이는 알고리즘 문제이다.

1) 초기 알고리즘

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
// 3234
// 4332 211
string solution(string number, int k) 
{
    string answer = "";
    vector<int> n1;
    for(int i=0;i<number.length();i++)
        n1.push_back(number[i]-'0');
    vector<int>n2=n1;
    sort(n1.begin(),n1.end());
    map<int,int> r;
    int count=0;
    for(int i=0;i<k;i++)
    {
        r[n1[i]]++;
        if(n1[i]==n1[k-1])
            count++;
    }
    
    // 477584
    // 877544 2211
    cout<<n1[k-1]<<endl;
    cout<<count<<endl;
    for(int i=0;i<number.length();i++)
    {
        if(number[i]-'0'>n1[k-1])
            answer+=number[i];
        else if(number[i]-'0'==n1[k-1])
        {
            if(count>0)
                count--;
            else
                answer+=number[i];
        }
        else
            continue;
    }
    
    return answer;
}

1232134
→ 1122334

① 문자열에 포함된 숫자를 오름차순으로 정렬

if k==3
→ 112를 제거

② 앞에서부터 k개의 숫자가 제거할 숫자

1 -> 제거
2 -> 제거
3
1->제거
234
→ 3234

③ 문자열의 앞에서부터 제거할 숫자와 일치하면 제거

위 알고리즘 풀이의 경우 다음과 같은 반례가 발생한다.

2) 반례 확인

입력 : "4177252841"
출력 : "477584"
→ 정답 : "775841"

반례가 발생하는 이유는 모든 자릿수에 따른 가중치를 고려하지 않았으므로.

2. 풀이 ②

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    // nsize : answer의 길이
    int nsize=number.size()-k;
    int idx=0;
    for(int i=0;i<nsize;i++)
    {
        char max=number[idx];
        int maxid=idx;
        for(int j=idx;j<=k+i;j++)
        {
            if(max<number[j])
            {
                max=number[j];
                maxid=j;
            }
        }
        idx=maxid+1;
        answer+=max;
    }
    return answer;
}

① 구간 내 최댓값을 찾아 answer를 갱신하는 방식

"4177252841"

idx=0 maxid=0 j=0~j=4 -> answer=7
idx=3 maxid=2 j=3~j=5 -> answer=77
idx=4 maxid=3 j=4~j=6 -> ansewr=775
...

answer="775841"