programmers) 체육복

프로그래머스 체육복 Java 풀이

이번에는 프로그래머스 그리디 유형의 체육복 문제를 풀었다.

체육복 문제는 그리디 입문 문제로 많이 언급되는 문제이다.
문제 자체는 어렵게 느껴지지 않았지만, 실제로 풀면서 연산자 실수 때문에 잠깐 헤맸다.

특히 +=를 써야 하는 부분에서 =+처럼 작성하면서 값이 예상과 다르게 나왔고, 디버깅하여 실수를 확인하고 수정하였다.

---

문제 정보

항목내용

문제	프로그래머스 체육복
유형	그리디
사용 언어	Java
핵심 자료구조	int 배열
주요 개념	학생별 체육복 개수 관리, 앞뒤 학생에게 빌려주기
시간복잡도	O(N log N)
공간복잡도	O(N)
풀이시간	40분
결과	통과

---

문제 설명 정리

전체 학생 수 n이 주어진다.
일부 학생은 체육복을 도난당했고, 일부 학생은 여벌 체육복을 가지고 있다.

체육복을 도난당한 학생은 수업을 들을 수 없지만, 바로 앞번호나 바로 뒷번호 학생에게 여벌 체육복을 빌릴 수 있다.

즉, i번 학생이 여벌 체육복을 가지고 있다면 다음 학생에게만 빌려줄 수 있다.

i - 1번 학생
i + 1번 학생

목표는 체육수업을 들을 수 있는 학생 수의 최댓값을 구하는 것이다.

---

입출력 예시로 이해하기

예를 들어 다음과 같은 입력이 있다고 하자.

n = 5
lost = [2, 4]
reserve = [1, 3, 5]

학생은 총 5명이다.

학생 번호상태

1	여벌 있음
2	도난당함
3	여벌 있음
4	도난당함
5	여벌 있음

1번 학생은 2번 학생에게 체육복을 빌려줄 수 있다.
3번 학생은 4번 학생에게 체육복을 빌려줄 수 있다.

그러면 모든 학생이 체육수업을 들을 수 있다.

---

문제를 보고 떠올린 생각

처음에는 각 학생의 체육복 개수를 배열로 관리하면 되겠다고 생각했다.

학생은 기본적으로 체육복을 1벌 가지고 있다.

기본 상태: 1벌
여벌이 있으면: +1
도난당했으면: -1

그래서 학생별 체육복 상태를 다음과 같이 표현했다.

값의미

0	체육복이 없음
1	체육복이 1벌 있음
2	여벌 체육복까지 있음

이렇게 하면 lost와 reserve에 동시에 포함된 학생도 자연스럽게 처리할 수 있다.

예를 들어 어떤 학생이 여벌 체육복도 있고 도난도 당했다면:

기본값 1
여벌 +1 → 2
도난 -1 → 1

결과적으로 본인이 입을 체육복 1벌만 남게 된다.

---

풀이 아이디어

풀이 흐름은 다음과 같이 잡았다.

1. 학생 수보다 1 큰 배열을 만든다.
2. 모든 학생의 체육복 개수를 1로 초기화한다.
3. reserve 학생은 +1 한다.
4. lost 학생은 -1 한다.
5. 왼쪽부터 차례대로 확인하면서 여벌이 있는 학생이 앞번호 또는 뒷번호 학생에게 빌려준다.
6. 체육복 개수가 1 이상인 학생 수를 센다.

학생 번호가 1번부터 시작하므로 배열 크기는 n + 1로 만들었다.

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

0번 인덱스는 사용하지 않고, 1번 학생부터 n번 학생까지 사용했다.

---

내가 작성한 풀이

import java.util.*;

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

        for (int i = 1; i < student_clothes.length; i++) {
            student_clothes[i] = 1;
        }

        Arrays.sort(reserve);
        Arrays.sort(lost);

        for (int i : reserve) {
            student_clothes[i] += 1;
        }

        for (int i : lost) {
            student_clothes[i] -= 1;
        }

        for (int i = 1; i < student_clothes.length; i++) {
            if (student_clothes[i] > 1) {
                if (i - 1 > 0 && student_clothes[i - 1] == 0) {
                    student_clothes[i - 1] += 1;
                    student_clothes[i] -= 1;
                } else if (i + 1 < student_clothes.length && student_clothes[i + 1] == 0) {
                    student_clothes[i + 1] += 1;
                    student_clothes[i] -= 1;
                }
            }
        }

        int answer = 0;

        for (int item : student_clothes) {
            if (item > 0) {
                answer++;
            }
        }

        return answer;
    }
}

---

그리디로 생각한 부분

이 문제에서 그리디하게 생각한 부분은 여벌 체육복이 있는 학생이 빌려줄 수 있는 학생에게 바로 빌려주는 것이다.

나는 학생 번호를 왼쪽부터 차례대로 확인했다.
그리고 여벌이 있는 학생을 만나면 먼저 앞번호 학생을 확인했다.

if (i - 1 > 0 && student_clothes[i - 1] == 0) {
    student_clothes[i - 1] += 1;
    student_clothes[i] -= 1;
}

앞번호 학생에게 빌려줄 수 없다면 뒷번호 학생을 확인했다.

else if (i + 1 < student_clothes.length && student_clothes[i + 1] == 0) {
    student_clothes[i + 1] += 1;
    student_clothes[i] -= 1;
}

왼쪽부터 순서대로 확인할 때는 앞번호 학생을 먼저 챙기는 방식이 자연스럽다고 생각했다.
이미 지나간 학생은 다시 확인하지 않기 때문에, 현재 학생이 앞번호 학생을 도울 수 있다면 먼저 도와주는 것이 좋다고 판단했다.

---

실수한 부분: +=를 =+로 작성함

이번 풀이에서 헤맸던 부분은 연산자 실수였다.

체육복 개수를 1 증가시키려면 아래처럼 작성해야 한다.

student_clothes[i] += 1;

그런데 처음에 실수로 아래처럼 작성했다.

student_clothes[i] =+ 1;

처음에는 비슷해 보여서 바로 눈에 들어오지 않았다.
하지만 두 코드는 의미가 완전히 다르다.

코드의미

x += 1	기존 값에 1을 더한다
x =+ 1	+1을 대입한다
x -= 1	기존 값에서 1을 뺀다
x =- 1	-1을 대입한다

즉, +=는 누적 연산이고, =+는 양수 값을 대입하는 코드이다.

특히 =- 1처럼 작성하면 기존 값에서 1을 빼는 것이 아니라, 아예 -1을 대입하는 의미가 된다.

이번에 값이 이상하게 -1로 나와서 디버깅하다가 이 부분을 발견했다.
앞으로 누적 연산을 사용할 때는 +=, -= 방향을 꼭 확인해야겠다.

---

시간복잡도

이 풀이에서는 reserve와 lost 배열을 정렬했다.

Arrays.sort(reserve);
Arrays.sort(lost);

정렬이 들어가기 때문에 시간복잡도는 다음과 같이 볼 수 있다.

O(R log R + L log L + N)

여기서 R은 reserve 배열의 길이이고, L은 lost 배열의 길이이다.

기호의미

N	전체 학생 수
R	reserve 배열 길이
L	lost 배열 길이

reserve와 lost의 길이는 최대 N까지 가능하므로, 전체적으로는 다음처럼 볼 수 있다.

O(N log N)

내가 생각한 것처럼 정렬이 들어가므로 O(N log N) 으로 판단했다.

다만 정렬을 제외한 반복문은 대부분 한 번씩 순회하는 구조라 O(N)이다.

---

공간복잡도

학생별 체육복 개수를 저장하기 위해 n + 1 크기의 배열을 사용했다.

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

따라서 공간복잡도는 다음과 같다.

O(N)

학생 수만큼 배열을 추가로 사용했기 때문이다.

---

엣지 케이스

체육복 문제에서 조심해야 하는 케이스는 다음과 같다.

케이스설명

잃어버렸지만 여벌도 있는 학생	결과적으로 본인 체육복 1벌만 남음
1번 학생	앞번호 학생이 없으므로 i - 1 > 0 확인 필요
n번 학생	뒷번호 학생이 없으므로 i + 1 < length 확인 필요
앞뒤 모두 빌려줄 수 있는 경우	어떤 방향을 먼저 볼지 기준 필요
아무도 빌려줄 수 없는 경우	체육복 0인 학생은 수업 불가

내 풀이에서는 학생별 체육복 개수를 배열로 관리했기 때문에,
lost와 reserve에 동시에 포함된 학생도 자연스럽게 처리됐다.

---

다른 풀이

다른 풀이를 보면서 인상적이었던 부분은 `Math.abs(lost[i] - reserve[j]) == 1` 조건이었다.

처음에는 앞번호 학생과 뒷번호 학생을 각각 `i - 1`, `i + 1`로 나누어 확인했다.  
그런데 문제 조건을 다시 보면 체육복은 바로 앞번호 또는 바로 뒷번호 학생에게만 빌려줄 수 있다.

즉, 두 학생 번호의 차이가 1이면 빌려줄 수 있다는 뜻이다.

그래서 `Math.abs()`를 사용하면 앞번호인지 뒷번호인지 따로 나누지 않고, 두 학생 번호의 차이만으로 빌릴 수 있는지 판단할 수 있었다.

if (Math.abs(lost[i] - reserve[j]) == 1) {
    reserve[j] = -1;
    answer++;
    break;
}

---

더 간단한 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);

        int answer = n - lost.length;

        // 1. lost와 reserve에 둘 다 있는 학생 처리
        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] == reserve[j]) {
                    lost[i] = -1;
                    reserve[j] = -1;
                    answer++;
                    break;
                }
            }
        }

        // 2. 여벌 체육복 빌려주기
        for (int i = 0; i < lost.length; i++) {
            if (lost[i] == -1) continue;

            for (int j = 0; j < reserve.length; j++) {
                if (reserve[j] == -1) continue;

                if (Math.abs(lost[i] - reserve[j]) == 1) {
                    reserve[j] = -1;
                    answer++;
                    break;
                }
            }
        }

        return answer;
    }
}

---

이번 문제 회고

항목내용

풀었는가?	풀이 완료
문제 해석	학생별 체육복 수를 관리하면 된다고 이해함
자료구조 선택	int 배열 사용
그리디 기준	앞번호 학생을 먼저 확인하고, 불가능하면 뒷번호 학생 확인
구현 실수	+=를 =+로 잘못 작성함
디버깅 포인트	값이 -1로 나와 연산자 실수를 발견함
시간복잡도 판단	정렬 때문에 O(N log N)
공간복잡도 판단	학생 수만큼 배열을 사용하므로 O(N)

---

다시 풀 때 주의할 점

다시 풀 때는 아래 부분을 주의해야겠다.

1. lost와 reserve에 동시에 있는 학생을 먼저 고려한다.
2. 학생 번호는 1번부터 시작하므로 배열 인덱스를 조심한다.
3. 1번 학생과 n번 학생은 앞뒤 범위 체크를 해야 한다.
4. 왼쪽부터 확인할 때는 앞번호 학생을 먼저 챙기는 기준을 명확히 한다.
5. +=와 =+를 헷갈리지 않는다.

특히 이번 문제에서는 알고리즘 자체보다 연산자 실수 때문에 시간이 더 걸렸다.
값이 이상하게 고정되거나 -1이 나온다면, +=, -=, =+, =-를 먼저 확인해봐야겠다.

---

마무리

이번 체육복 문제는 그리디 입문 문제로 좋았다.

문제 자체는 “여벌이 있는 학생이 앞뒤 학생에게 체육복을 빌려준다”는 단순한 구조였지만,
실제로 코드로 구현할 때는 학생별 상태를 어떻게 관리할지, 어떤 순서로 빌려줄지 정해야 했다.

내 풀이에서는 student_clothes 배열을 사용해서 학생별 체육복 개수를 관리했고,
왼쪽부터 순회하면서 여벌이 있는 학생이 앞번호 학생을 먼저 도와주는 방식으로 풀었다.

이번 문제에서 가장 크게 배운 점은 두 가지이다.

첫째, 그리디 문제는 선택 기준을 명확히 해야 한다.
둘째, +=와 =+는 완전히 다르다.

앞으로 그리디 문제를 풀 때는 먼저 “무엇을 기준으로 선택할 것인가”를 정리하고,
구현할 때는 단순한 연산자 실수도 꼼꼼히 확인해야겠다.