LV2_큰 수 만들기

여윽시 그리디다

앞으로 그리디는 조오금 다른 방향으로 생각을 하는 힘을 길러야 겠다. 답을 보면 너무 쉬운데 안보면 너무 어렵

 

 

 

첫 생각

ex) 4177252341 에서 4개 수 지우려고 할때...

 

for(int i = 0 ; i < size() ; i++)에 대한 

max_num을 구하고.. 

0->2->6 이니 prev인 2개를 앞에 지우고 뭐시기 해서

뭐시기 하는데 구현법이 너무 복잡하고 예외도 너무 많이 나와서 못풀었다..

 

 

 

 

 

 

 

 

 

답안 :

4177252341 에서 4개 수 지우려고 할때 -> 6개수를 써야 한다.

 

그러면 

첫번재부터 size-6 까지중에서 max 인 것 (pos)

pos+1째부터 size-5 까지중에서 max 인것 (pos2)

pos2+1째부터 size-4 까지중에서 max 인것

.............

하면 된다.

 

 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define pii pair<int, int>
using namespace std;
 
string solution(string num, int k)
{
    int size = num.size();
    string ans = "";
    int pos = -1;
    for (int i = 0; i < (size-k); i++)
    {
        int max = -1;
        
        for (int j = pos+1; j <= k+i; j++)
        {
            if (max < num[j] - '0')
            {
                max = num[j] - '0';
                pos = j;
            }
        }
    
        ans += num[pos];
        //cout << ans << '\n';
    }
 
    return ans;
 
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    string number = "4177252841";
    int k = 4;
 
    cout << solution(number, k);
}