[프로그래머스] 체육복 (탐욕법(Greedy))

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    map<int, int> m;
    sort(reserve.begin(), reserve.end());
    sort(lost.begin(), lost.end());
    for(int i=0; i<lost.size(); i++){
        for(int j=0; j<reserve.size(); j++){
            if(m.count(reserve[j])==0){
                if(reserve[j]==lost[i]-1||reserve[j]==lost[i]+1){
                    m.insert(make_pair(reserve[j], lost[i]));
                    break;
                }
            }
                
        }
    }
    answer=m.size()+(n-lost.size());
    return answer;
}

- sort 전: 정확성 58.3(5/12), sort 후: 66.7(8/12)

 

4개의 테스트케이스에 대해서는 

n=3, lost: [1,2] reserve: [2,3]일 때 return이 2인 경우이다. 즉, "여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다."라는 제한사항에 대한 케이스이다. 따라서 이 케이스에서는 lost[i]와 reserve[j]가 같은 경우일 때도 make_pair를 하도록 한다.

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    map<int, int> m;
    sort(reserve.begin(), reserve.end());
    sort(lost.begin(), lost.end());
    for(int i=0; i<lost.size(); i++){
        for(int j=0; j<reserve.size(); j++){
            if(m.count(reserve[j])==0){
                if(reserve[j]==lost[i]-1||reserve[j]==lost[i]+1||reserve[j]==lost[i]){
                    m.insert(make_pair(reserve[j], lost[i]));
                    break;
                }
            }   
        }
    }
    answer=m.size()+(n-lost.size());
    return answer;
}

answer에서 lost와 reserve에 둘다 없는거: 체육복을 가져왔는데 여벌이 없는 사람 -> answer에 따로 추가

 

to be continued..

 

answer에 들어가는 것

1. n 이하 수 중에서 lost와 reserve에 없는 수 (여벌은 없는데 체육복 있는 사람)

2. lost와 reserve에서 중복되는 수 (여벌을 잃어버렸고(lost), 남은 체육복 하나 있는 사람(reserve))

3. reserve에 원소가 lost의 원소보다 1 크거나 1 작은 경우