[프로그래머스] 체육복 (그리디)

문제 소개

오늘 풀었던 체육복 - 프로그래머스 문제를 정리합니다.
이 문제는 체육복이 없는 학생에게 여벌 체육복을 빌려줘 가능한 최대 학생 수를 구하는 그리디 유형 문제입니다. 핵심은 "양쪽 학생만 빌려줄 수 있음"과 "여벌이 있지만 도난당한 경우 빌려줄 수 없음" 조건을 처리하는 데 있습니다.

문제 링크: 체육복 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 학생 상태를 배열로 관리 (기본값 0, 도난 -1, 여벌 +1)
2. 여벌 + 도난 중복 학생은 0으로 정리
3. 왼쪽 또는 오른쪽 학생에게만 빌려주는 탐욕적 할당 방식(그리디)
   현재 시점에서 가장 가까운(왼쪽부터) 학생에게 먼저 빌려주는 방식이 전체 학생 수를 최대로 만드는 결정
   
4. 끝까지 체육복 못 받은 학생 수만큼 전체 인원에서 차감

---

해결 과정 및 코드

핵심 아이디어

1. students[] 배열을 통해 각 학생의 체육복 상태를 정수값으로 표현
   • 기본값 0, 도난 시 -1, 여벌 시 +1
2. 먼저 도난, 여벌 반영 후
   • 여벌 + 도난 학생은 자연스럽게 0 처리됨
3. 왼쪽(i-1)이나 오른쪽(i+1)에 여벌이 있는 경우 빌려줌
   • 가장 먼저 왼쪽(i-1) 확인, 없으면 오른쪽(i+1) 확인
4. 어느 쪽에서도 못 빌리면 최종 수업 인원에서 차감

코드

시간 복잡도 : O(N)

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] students = new int[n + 2];  // index 0, n+1은 패딩
        int answer = n;

        // 도난 처리
        for (int l : lost)
            students[l]--;

        // 여벌 처리
        for (int r : reserve)
            students[r]++;

        // 도난 상태 복구 시도
        for (int i = 1; i <= n; i++) {
            if (students[i] != -1) continue;

            // 왼쪽에서 빌리기
            if (students[i - 1] == 1) {
                students[i]++;
                students[i - 1]--;
            }
            // 오른쪽에서 빌리기
            else if (students[i + 1] == 1) {
                students[i]++;
                students[i + 1]--;
            }
            // 못 빌렸으면 수업 불가
            else answer--;
        }

        return answer;
    }
}