프로그래머스 n+1카드게임 c++ // 그리디, 집합을 분류하라

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

프로그래머스

1. 시행착오

1. 완탐 ? -> 

경우의수 : 선택안함, 좌측선택, 우측선택, 둘다선택 (4) ^ 1000(n) ->불가

2. dp?

상태 : [idx][round][mycard] == 1000*1000*1000 == 10억 -> 메모리초과 -> 불가

// mycard (내가 갖고있는 카드)부분을 정수 1개의 상태로 표현 불가능 -> 불가!

3. 그리디? 부분최적해가 전체최적해가 된다.

 

2. 의사코드

0. 매순간마다 고르는게 아니라 avail에 넣고, 필요한경우(부분최적해) 코인이 있으면 사용한다!

1. 카드집합를 세부분으로 나누기 : mycard, 남은카드 , 이용가능한 카드

2. 기저사례 : remain.size()==0 //남은 카드가 더 없는경우

n+1을 맞추는 카드가 없는경우

3. 매 라운드마다 remain에서 2개씩 빼서 avail에 넣기!

4. 내카드만으로 n+1 만들수있으면 그렇게함, 쓴카드는 pop

5. 내카드1개, 이용가능카드1개로 n+1 만들수있으면 그렇게함, 쓴카드는 pop

6. 이용가능카드만으로 n+1 만들수있으면 그렇게함, 쓴카드는 pop

7. 위경우에 안결렸다? -> n+1못만듬 -> 반복문 탈출

8. 원소 삭제가 자주일어남 -> set에 저장 (logN)

 

9.check(set& s) : s안에 n+1이 되는 두 쌍이 있는지, 있으면 그 두쌍 삭제 //&붙여야 진짜원본이 삭제됨

9.1. vector에 복사, 정렬

9.2. 이분탐색으로 있는지 탐색, 해당원소들 삭제 

9.3. 시간복잡도 : 복사 [set는 접근이 logN임](N * logN) + 정렬(NlogN) + 이분탐색(logN) == 유사 N log N

 

10. 전체시간복잡도 : N(전체원소) * NlogN(check) == 유사 N^2 logN -> 가능

 

3.전체코드

#include <bits/stdc++.h>

using namespace std;

int ret, n, vis[1004]; //해당동전을 갖고있는지
//vector<int> v; //현재 갖고있는 숫자들
vector<int> cards;

//set 두쌍 안에서 두쌍의합이 n+1이 있는지
//있으면, 그 두 쌍 삭제
int check2(set<int>& s1, set<int>& s2){
    vector<int> v1,v2;
    for(auto i : s1) v1.push_back(i);
    sort(v1.begin(),v1.end());
    for(auto i : s2) v2.push_back(i);
    sort(v2.begin(),v2.end());
    
    for(int i=0;i<v1.size();++i){
        if(binary_search(v2.begin(),v2.end(),(n+1)-v1[i])){
            s1.erase(v1[i]);
            s2.erase(v2[lower_bound(v2.begin(),v2.end(),n+1-v1[i]) - v2.begin()]);
            return 1;
        }
    }
   return 0;
}
//set 안에서 두쌍의합이 n+1이 있는지
//있으면, 그 두 쌍 삭제
int check1(set<int>& s){
    vector<int> v;
    for(auto i : s) v.push_back(i);
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();++i){
        if(binary_search(v.begin(),v.end(),(n+1)-v[i])){
            s.erase(v[i]);
            s.erase(v[lower_bound(v.begin(),v.end(),n+1-v[i]) - v.begin()]);
            return 1;
        }
    }
   return 0;
}

int solution(int coin, vector<int> _cards) {
    n=_cards.size();
    cards=_cards;
    
    set<int> mycard;
    deque<int> remain;
    set<int> avail;

    for(int i=0;i<n;++i){
        if(i<n/3) mycard.insert(cards[i]);
        else remain.push_back(cards[i]);
    }
    
    
    ret=1;
    //1라진행
    while(1){
        if(remain.size()==0) break;
        int a,b;
        a=remain.front();
        remain.pop_front();
        b=remain.front();
        remain.pop_front();
        avail.insert(a);
        avail.insert(b);
        
        // for(auto i : mycard) cout<<i<<" "; cout<<"\n";
        // for(auto i : remain) cout<<i<<" "; cout<<"\n";
        // for(auto i : avail) cout<<i<<" "; cout<<"\n";
        // cout<<"\n";
        
        if(check1(mycard)){
            ret++;
            continue;
        }
        if(check2(mycard,avail) && coin>=1){
            ret++;
            coin-=1;
            continue;
        }
        if(check1(avail) && coin>=2){
            ret++;
            coin-=2;
            continue;
        }
        break;
    }
    
    
    
    
    
    return ret;
}

 

4. 개선

탐색부분을 set.find(n+1 - val) != set.end() 로 하면  logN에 처리 가능하다!

set.find(val) // 있는경우 val.idx리턴, 없으면 set.end() 리턴

기존 : 정렬후 이분탐색 : nlogn + log n

void solve(int val, int& coin)
{
    int findval = n+1 - val;
    if (cur.find(findval) != cur.end() && coin){
        coin--;
        life++;
        cur.erase(findval);
    } else {
        if (pass.find(findval) != pass.end()){
            coinlife++;
            pass.erase(findval);
        } else {
            pass.insert(val);
        }
    }
}