'Programming Problems/Greedy'에 해당되는 글 1건

Programming Problems/Greedy

N digit 숫자를 K회 스왑해서 최댓값 만들기

ex ) 8799, K = 2 에서 ans = 9987


나이브하게는 모든 경우의 수를 만들어서 (N^2 ^ K) 스왑하고, 그 결과들 중에서 가장 큰 것을 찾는다 ( & data ) 이렇게 만들어서 한번에 하나씩 비교할 수 있을 듯. 그렇게 하면 비교가 N 시간이 걸리므로 O(N * N^2 ^ K) 시간이 걸리겠다.


여기서 더 가려면 규칙성을 찾는 그리디 알고리즘이나, 동적 계획법으로 풀게 되겠다. 자료구조를 이용한 해법은 없는 것 같다.


동적 계획법이 생각난다. 아니 그리디 솔루션인가..


그리디 솔루션을 살펴보자. 매 단계에서 자신이 할 수 있는 최선을 다하면 최대 결과가 만들어질까? 모든 숫자가 역순으로 정렬된 것이 아닌 이상 최대 뒤집기를 찾을 수 있다.

동적 계획법은 M이 n자리 10진법 수이기 때문에 10^N 개의 스테이트를 저장해야 해서 뭐 사실상 효과가 별로 없을 듯 시간 복잡도 상한도 그리 아름답지는 않고


핵심 생각법은 이거인거 같다.

M = 7899, K = 2 의 결과는 M = 9897, K = 1 의 결과와 동치이다.

이렇게 매 단계에서 최선을 다해 밀어붙이는게 성립하는 이유는, 그 최댓값 찾기 알고리즘은 아래와 같이 동작하는데;

맨 왼쪽의 숫자부터 본인 오른쪽 중에서 최댓값을 찾아 스왑한다. 본인이 최댓값이면 오른쪽으로 하나 넘어간다.

모든 숫자가 그 위치의 최댓값이면 맨 오른쪽 두개를 스왑한다.


따라서 두번째의 경우에는 이미 최댓값인 상태에서 어느 두개를 스왑하든, 그 다음에 다시 그 두개를 스왑해야 최댓값을 얻을 수 있다. 그 다음에 스왑할 기회가 없을 수 있으니(홀수인 경우) 최소로 숫자를 감소시키는 맨 오른쪽 두개를 스왑하는 것이 최선이고 무조건 최댓값을 찾는다.


첫번째의 경우에는 만약 최댓값과 교환하지 않았다면 다음 경우는 무조건 최대 가능성보다 값이 작다. 그 후에도 숫자의 갯수는 똑같으므로 결국 최대값이 되기 위해 필요한 스왑은 똑같은데, 한번이라도 최대값과 스왑을 했을 경우에 그 자릿수는 최대값이 되어버리므로 추후에 스왑되지 않는다. 그런데 이렇게 최대 횟수로 최선의 스왑을 하지 않은 경우에는 무조건 결과값이 더 작을 수 밖에 없다.


따라서 이 알고리즘을 통하면 최댓값을 찾게 된다.


코딩 하겟읍니다.


void findmax(string &s, int K){
     multimap<char,int> buffer;

// fill buffer

for(int i = 0 ; i < s.size() ; i++){

buffer.insert(pair<char,int>(s[i],i));

}

// check buffer for swap position

int pivot = 0;

for(auto it = --buffer.end(); it!=buffer.begin() ; it--){

if(it->second == pivot) {

auto it2 = buffer.equal_range(it->first);

if(++it2->first!=it2->second){

--it2->first;

int pivot2;

for(auto i = it2->first ; i!=it2->second ; i++){

if(i->second!=it->second) pivot2 = i->second;

}

swap(s[pivot],s[pivot2]);

findmax(s,K-1);

break;

}else{

pivot++;

continue;

}

else{

swap(s[pivot], s[it->second]);

findmax(s,K-1);

break;

}

}

return;

}


시간 복잡도 : O(NlogN * K)

공간 복잡도 : O(N * K)



'Programming Problems > Greedy' 카테고리의 다른 글

N digit 숫자를 K회 스왑해서 최댓값 만들기  (0) 2018.04.22