[프로그래머스] 체육복 - Java

• 프로그래머스 문제 URL

---

문제 요약

전체 학생 수 n이 주어지고, 체육복을 도난당한 학생 목록(lost) 과 여벌이 있는 학생 목록(reserve) 이 주어질 때, 체육수업을 들을 수 있는 학생 수의 최댓값을 구하는 문제다.
학생은 자기 번호 기준으로 앞/뒤 학생(번호 차이 1) 에게만 체육복을 빌릴 수 있다.

---

핵심 아이디어

이 문제는 “체육복이 없는 학생(0장)을 발견했을 때, 지금 당장 빌릴 수 있으면 빌린다”는 방식으로 최댓값을 만들 수 있어 Greedy로 접근한다.
특히 한 학생이 빌릴 수 있는 후보는 최대 2명(왼쪽/오른쪽)뿐이라, 배열로 상태를 만들어두고 순서대로 해결하는 방식이 구현이 깔끔하다.

---

상태 설계: studentByCloth[]로 정리

이 코드는 학생별 체육복 개수를 배열로 관리한다.

• studentByCloth[i] = (i+1)번 학생이 가진 체육복 개수
• 초기값은 모두 1로 시작
• lost면 1 감소, reserve면 1 증가

int[] studentByCloth = new int[n];
Arrays.fill(studentByCloth, 1);

for (int lostStudent : lost) {
    studentByCloth[lostStudent - 1]--;
}
for (int reserveStudent : reserve) {
    studentByCloth[reserveStudent - 1]++;
}

이렇게 해두면 “도난이면서 여벌도 있는 학생”은 결과적으로 1장이 되어(0도 2도 아닌) 자연스럽게 정리된다.

---

빌리기 로직

핵심은 “0장인 학생을 발견하면” 빌릴 수 있는지 확인하는 것.

for (int i = 0; i < n; i++) {
    if (studentByCloth[i] == 0) {
        if (i > 0 && studentByCloth[i - 1] >= 2) {
            studentByCloth[i - 1]--;
            studentByCloth[i]++;
        } else if (i + 1 < n && studentByCloth[i + 1] >= 2) {
            studentByCloth[i + 1]--;
            studentByCloth[i]++;
        }
    }
}

여기서 포인트는:

• 없는 학생 기준(0장) 으로만 처리해서 로직이 단순해진다.
• 왼쪽이 가능하면 왼쪽에서 먼저 빌리고, 아니면 오른쪽을 본다.
• 인덱스 범위(i > 0, i + 1 < n) 체크로 예외를 막는다.

---

정답 계산

마지막에는 1장 이상인 학생 수를 세면 된다.

int answer = 0;
for (int a : studentByCloth) {
    if (a >= 1) answer++;
}
return answer;

---

전체 코드(제출용)

import java.util.Arrays;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] studentByCloth = new int[n];

        Arrays.fill(studentByCloth, 1);

        for (int lostStudent : lost) {
            studentByCloth[lostStudent - 1]--;
        }
        for (int reserveStudent : reserve) {
            studentByCloth[reserveStudent - 1]++;
        }

        for (int i = 0; i < n; i++) {
            if (studentByCloth[i] == 0) {
                if (i > 0 && studentByCloth[i - 1] >= 2) {
                    studentByCloth[i - 1]--;
                    studentByCloth[i]++;
                } else if (i + 1 < n && studentByCloth[i + 1] >= 2) {
                    studentByCloth[i + 1]--;
                    studentByCloth[i]++;
                }
            }
        }

        for (int a : studentByCloth) {
            if (a >= 1) answer++;
        }

        return answer;
    }
}