[알고리즘] 체육복

포인트

• 그리디 문제 (부분적인 최적해가 전체적인 최적해가 되는 법)
• 앞의 사람에서 빌려 줄 수 있는가? 뒷에 사람에서 빌려 줄 수 있는가?

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <vector>
#include <iostream>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> total(n, 1); //총 인원수만큼 벡터를 생성하고 체육복갯수 1로 설정
    for (auto ele : lost) total[ele - 1]--; //체육복을 잃어버린 사람은 1개 마이너스
    for (auto ele : reserve) total[ele - 1]++; //체육복을 여분으로 가져왔다면 1개 플러스
    //처음부터 돌면서 순회하기
    for (int i = 0; i < total.size(); i++) {
        //체육복이 0개라면
        if (!total[i]) {
            //앞의 사람이 여분이 있나 확인하고 있다면 빌리기
            if (i != total.size() - 1 && total[i + 1] == 2) {
                total[i + 1] -= 1;
                total[i] += 1;
            }
                //뒤에 사람이 여분이 있나 확인하고 있다면 빌리기
            else if (i != 0 && total[i - 1] == 2) {
                total[i - 1] -= 1;
                total[i] += 1;
            }
        }
    }
    //체육복이 몇명이 있나 체크하기
    for (auto ele : total) if (ele != 0) answer++;
    return answer;
}

python

def solution(n: int, lost: list, reserve: list)->int:
    data = [1] * n
    # 기본적으로 체육복 1개씩 가지고 있다.
    for ele in lost:
        data[ele - 1] -= 1
        # 1개씩 빼준다.
    for ele in reserve:
        data[ele - 1] += 1
        # 1개씩 더해준다.

    for i in range(len(data)):
        if data[i] == 0:
            if i < len(data) - 1 and data[i + 1] == 2:
                # 끝이 아니고 다음 숫자가 2일 때 (마지막 수 고려)
                data[i] += 1
                data[i + 1] -= 1
            elif i > 0 and data[i - 1] == 2:
                # 0이 아니고 다음 숫자가 2일 때 (맨 처음 고려)
                data[i] += 1
                data[i - 1] -= 1

    return len(data) - data.count(0)


print(solution(5, [2, 4], [1, 3, 5]))
# 5
print(solution(5, [2, 4], [3]))
# 4
print(solution(3, [3], [1]))