[프로그래머스][C++] 체육복

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

풀이

1. 모든 학생들의 체육복 수 계산
    (1) 처음에 모든 학생들은 1개의 체육복을 가지고 있다.
    (2) 여벌의 체육복이 있는 학생: +1
    (3) 체육복을 도난당한 학생: -1
2. 1번 학생부터 체육복을 빌리는 경우 계산
    (1) 도난당한 학생(체육복 개수: 0)은 양옆의 학생에게 체육복을 빌릴 수 있는지(체육복 개수: 2) 확인한다.
    (2) 왼쪽 학생에게 우선적으로 빌린다.

 

🚨 전체 학생 인덱스 유의

• 학생 번호가 1번부터 시작하므로  n + 1
• n번째 학생이 오른쪽 학생을 탐색하는 경우가 존재하므로 n + 2

코드

#include <iostream>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;
    vector<int> clothes(n + 2, 1);  // 처음 학생이 가지고 있는 체육복 수: 1

    for (int i: reserve) {   // 여벌의 체육복이 있는 학생
        clothes[i]++;
    }
    for (int i: lost) {  // 체육복을 도난당한 학생
        clothes[i]--;
    }

    for (int i = 1; i <= n; i++) {
        if (clothes[i]) { // 체육복이 있음
            continue;
        }
        if (clothes[i - 1] == 2) {    // 왼쪽 학생에게 빌리기
            clothes[i - 1]--;
            clothes[i]++;
        } else if (clothes[i + 1] == 2) { // 오른쪽 학생에게 빌리기
            clothes[i + 1]--;
            clothes[i]++;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!clothes[i]) {
            answer--;
        }
    }

    return answer;
}