[프로그래머스 고득점kit] 그리디_체육복(c++)

https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=cpp 

프로그래머스

맨 처음에 푼 방법 

#include <string> // 처음 풀이
#include <vector>
#include <algorithm>

using namespace std;

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

이렇게 풀면 자기 여벌이 있지만 체육복을 잃어버린 학생때문에 밀리게 된다.

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n - lost.size();
    
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    for (int i = 0, j = 0; i < lost.size(); i++) // 여벌 있는데 잃어버리놈 미리 빼줌 안그러면 밀림
    {
        if (j >= reserve.size())
            break ;
        while (lost[i] > reserve[j] + 1)
            j++;  
        if (lost[i] == reserve[j])
        {
            lost[i] = -1;
            reserve[j] = -1;
            answer++;
            j++;
        }
    }
    
    for (int i = 0, j = 0; i < lost.size(); i++)
    {
        while (j < reserve.size() && reserve[j] == -1) // 미리 빼준 놈이면
            j++;
        if (lost[i] == -1) // 미리 빼준 놈이면
            continue;
        if (j >= reserve.size()) // 다 찾았으면
            return answer;
        if (lost[i] + 1 == reserve[j] || lost[i] - 1 == reserve[j]) // 빌려줄 수 있는 놈들끼리면
        {
            answer++;
            j++;
        }
    }
    return answer;
}

입력값 〉	13, [1, 2, 5, 6, 10, 12, 13], [2, 3, 4, 5, 7, 8, 9, 10, 11, 12]
기댓값 〉	11

이번엔 이 경우를 처리해 주지 못한다.

여분의 체육복 처리 부분이 쉽지 않았다.. 이 방법이 아닌거 같아서 질문 글을 찾아보니, int arr board를 만들어서 처리했다는 팁을 보고 최종 코드를 작성했다.

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    vector arr(n + 1, 1); // arr[0]은 안쓴다
    
    for (int i = 0; i < lost.size(); i++)
        arr[lost[i]] = 0; // 잃어버린 학생들 번호를 인덱스로 하는 arr의 값을 0으로 바꿔준다
    for (int i = 0; i < reserve.size(); i++)
        arr[reserve[i]]++; // 여벌의 체육복에 해당하는 번호를 인덱스로 하는 arr의 값을 하나 더해준다
    for (int i = 1; i <= n; i++)
    {
        if (arr[i] > 1) // 그 번호의 체육복이 두개 이상 존재하면
        {
            if (i != 1 && arr[i - 1] == 0) // 앞에 번호 친구가 체육복이 없으면
                arr[i - 1]++;
            else if (arr[i + 1] == 0) // 뒤에 번호 친구가 체육복이 없으면
                arr[i + 1]++;
        }
    }
    for (int i = 1; i <= n; i++)
        if (arr[i])
            answer++;
    return answer;
}

level 1문제치고 시간을 많이 잡아먹었다... 그리디 문제 많이 풀어봐야겠다