프로그래머스 체육복 JAVA 풀이 (그리디, 구현)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

점심시간에 일부 학생이 체육복을 도난당했다.

여벌 체육복을 가진 학생은 자신의 앞번호 또는 뒷번호 학생에게만 체육복을 빌려줄 수 있다.

최대한 많은 학생이 체육수업에 참여할 수 있도록 체육복을 빌려주는 문제이다.

---

📌 접근 방법

학생마다 체육복의 개수를 저장하는 배열을 생성하였다.

초기에는 모든 학생이 체육복을 1벌 가지고 있다고 가정한 뒤,

도난당한 학생은 1벌을 차감하고 여벌이 있는 학생은 1벌을 추가하였다.

 

이후 체육복이 없는 학생을 순서대로 확인하면서 앞 학생에게 먼저 빌릴 수 있는지 확인하고,

불가능하면 뒤 학생에게 빌려주는 그리디 방식으로 해결하였다.

마지막에는 체육복이 1벌 이상인 학생의 수를 세어 정답을 구하였다.

---

📌 핵심 아이디어

1. 학생 상태를 배열 하나로 관리

학생 번호를 그대로 인덱스로 사용하기 위해 n + 1 크기의 배열을 생성하였다.

모든 학생을 1벌로 초기화한 뒤 도난과 여벌을 반영한다.

int[] student = new int[n + 1];

for (int i = 1; i <= n; i++) {
    student[i] = 1;
}

for (int l : lost) {
    student[l]--;
}

for (int r : reserve) {
    student[r]++;
}

결과적으로 상태를 쉽게 관리할 수 있다.

• 0 : 체육복 없음
• 1 : 체육복 1벌
• 2 : 여벌 있음

---

2. 앞 학생을 우선으로 빌려준다.

앞 학생에게 먼저 빌려주고, 불가능한 경우에만 뒤 학생에게 빌려준다.

현재 상황에서 가장 좋은 선택을 하는 그리디(Greedy) 전략이다.

if (p > 1 && student[p - 1] == 2) {
    student[p]++;
    student[p - 1]--;
} else if (p < n && student[p + 1] == 2) {
    student[p]++;
    student[p + 1]--;
}

---

3. 체육복을 가진 학생 수 계산

최종적으로 체육복이 1벌 이상인 학생의 수를 세어 반환한다.

for (int i = 1; i <= n; i++) {
    if (student[i] >= 1) {
        answer++;
    }
}

---

📌 전체 코드

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

        for (int i = 1; i <= n; i++) {
            student[i] = 1;
        }

        for (int l : lost) {
            student[l]--;
        }

        for (int r : reserve) {
            student[r]++;
        }

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

        for (int i = 1; i <= n; i++) {
            if (student[i] >= 1) {
                answer++;
            }
        }

        return answer;
    }
}

---

📄 정리

• 학생별 체육복 개수를 배열 하나로 관리하여 구현을 단순화했다.
• 학생 번호를 그대로 사용하기 위해 n + 1 크기의 배열을 사용했다.
• 앞 학생을 우선 확인한 뒤 뒤 학생을 확인하는 그리디 전략으로 해결했다.
• 도난과 여벌 상태를 배열 값(-1, +1)으로 처리하면 코드가 간결해진다.