프로그래머스 : 숫자게임 C++

programmers.co.kr/learn/courses/30/lessons/12987?language=cpp

코딩테스트 연습 - 숫자 게임

후기

1. 처음에 단순하게 순열로 생각했다가 시간초과 떳다

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

vector<int> AA;
int visited[100001]={0,};
int answer = 0;

void play_game(vector<int> new_b)
{
    int temp=0;
    for(int i=0;i<AA.size();i++)
    {
        if(new_b[i]>AA[i])
            temp++;
    }
    answer = max(answer,temp);
}


void make_team(int cnt,vector<int> B,vector<int> new_b)
{
    if(cnt == B.size())//순서 다 정해진거
    {
        play_game(new_b);
        return;
    }
    
    for(int i=0;i<B.size();i++)
    {
        if(visited[i]==0)
        {
            visited[i]=1;
            new_b[cnt] = B[i];
            make_team(cnt+1,B,new_b);
            visited[i]=0;
        }
    }
    
}


int solution(vector<int> A, vector<int> B) {
    for(int i=0;i<A.size();i++)
        AA.push_back(A[i]);
    
    vector<int> new_b(B.size());
    
    make_team(0,B,new_b);
    
    return answer;
}

 

2. 그래서 구글링을 조금 해서 참고했다

1) 내림차순으로 A랑 B 쭉 정렬

2) A[i] 보다 큰 B[i]있으면 B가 이길 수 있는거니까 answer++;

3) 어차피 인당 1게임밖에 못하니까 순서는 노상관!!!

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    int a=0;
    int b=0;
    
    sort(A.begin(),A.end(),greater<int>());
    sort(B.begin(),B.end(),greater<int>());
    
    for(int i=0;i<A.size();i++)
    {
        if(A[a]<B[b])
        {
            b++;
            answer++;
        }
        a++;
    }
    return answer;
}

 

역시나는 복잡한 구현보다 이런 효율적인 알고리즘 구현이 더 어려운거같다