[프로그래머스] 체육복

체육복

🔍 알고리즘 분류

• 그리디

💡 문제 풀이

1. n+1만큼 학생 배열 student 생성 후 1로 초기화
2. lost에 있는 학생을 student에서 찾아 체육복 개수 감소
3. reserve에 있는 학생을 student에서 찾아 체육복 개수 증가
4. student 배열 순회하며 체육복 개수가 0이라면
   1) 앞 학생의 체육복이 2개라면 student[i-1]--, student[i]++
   2) 뒷 학생의 체육복이 2개라면 student[i+1]--, student[i]++
5. student에 있는 학생 중 체육복 개수가 1 이상일 때 answer++

📄 코드

• C++

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    // 학생 배열 생성 후 1로 초기화
    vector<int> student(n + 1, 1);
    
    // 체육복 없는 학생들 체육복 개수 감소
    for (auto elem : lost) {
        student[elem]--;
    }
    
    // 체육복 2개인 학생들 체육복 개수 증가
    for (auto elem : reserve) {
        student[elem]++;
    }
    
    
    for (int i = 1; i <= n; i++) {
        // 현재 학생이 체육복이 없다면
        if (student[i] == 0) {
            // 앞 학생이 범위 내에 있고 체육복이 두 개라면
            if (i - 1 > 0 && student[i - 1] == 2) {
                // 앞 학생 체육복 감소
                student[i - 1]--;
                // 현재 학생 체육복 증가
                student[i]++;
                // 앞 학생에게 빌렸으니 뒷 학생은 확인 X
                continue;
            }
            
            // 뒷 학생이 범위 내에 있고 체육복이 두 개라면
            if (i + 1 <= n && student[i + 1] == 2) {
                // 뒷 학생 체육복 감소
                student[i + 1]--;
                // 현재 학생 체육복 증가
                student[i]++;
            }
        }
    }
    
    // 체육복이 1개 이상인 학생들만 카운트
    for (int i = 1; i <= n; i++) {
        if (student[i] > 0) answer++;
    }
    
    return answer;
}