[프로그래머스/C++] 알고리즘 고득점 키트 - 체육복

문제

---

첫 번째 나의 풀이 

해시맵을 이용해서 여벌의 옷이 있는 학생들을 관리했고,
자기 자신이 잃어버렸는데 여벌 가져온 경우부터 체크해서 실제로 옷을 빌려야하는 학생들 벡터를 새로 만들었다.(realLost)
그리고 realLost학생들을 기준으로 자신보다 앞 번호에 있는 학생들부터 여벌이 있는지 검사하면서 확인했다.
해시를 쓰게 되다보니 realLost학생이 정렬이 되어 있지 않는 경우 최적해를 낼 수 없게된다.
-> 그래서 13번 테스트케이스에서 계속 실패를 했었다..
-> sort함수 쓰고 그럴바에 그냥 배열로 순서대로 접근하는게 좋을 것 같다는 생각이 들었따..!

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    unordered_map<int,int> hMap;
    int answer = 0;
    vector <int> realLost;
    for (auto a:reserve){
        hMap[a]=1;
    }
    for (auto a: lost){
        if (hMap[a]){
            hMap[a]--;
            continue;
        }
        realLost.push_back(a);
    }
    sort(realLost.begin(),realLost.end());
    for (auto a:realLost){
        if (hMap[a-1]>0){
            hMap[a-1]--;
        }else if (hMap[a+1]>0){
            hMap[a+1]--;
        }else{
            n--;
        } 
    }
    answer = n;
    return answer;
}

 

아래는 많은 사람들이 푼 풀이로, 배열로 접근한다.
다음에 까먹을 때 쯔음, 한 번더 이렇게 다시 풀어봐야겠다.

#include <string>
#include <vector>

using namespace std;
int student[35];
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    for(int i : reserve) student[i] += 1;
    for(int i : lost) student[i] += -1;
    for(int i = 1; i <= n; i++) {
        if(student[i] == -1) {
            if(student[i-1] == 1) 
                student[i-1] = student[i] = 0;
            else if(student[i+1] == 1) 
                student[i] = student[i+1] = 0;
        }
    }
    for(int i  = 1; i <=n; i++)
        if(student[i] != -1) answer++;

    return answer;
}