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

승래·2026년 1월 3일

Lv1-체육복

문제

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

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

요구사항

인접한 번호만 대여 가능: 바로 앞 번호의 학생(i-1)이나 바로 뒷 번호의 학생(i+1)에게만 체육복을 빌려줄 수 있다.

중복 도난 예외: 여벌 체육복을 가져온 학생이 도난을 당했을 수도 있다. 이때는 본인의 체육복을 하나만 가진 것으로 간주하여, 남에게 빌려줄 수 없다.

전체 학생 수 $N$ 은 2명 이상 30명 이하이다.

목표: 체육수업을 들을 수 있는 학생의 최댓값을 구하라.

접근 방식

이 문제는 그리디(Greedy, 탐욕법) 알고리즘을 사용해야 한다. 그리디란 "현재 상황에서 당장 최선인 선택을 하는 것"이다.

핵심 로직
전처리 (가장 중요): lost(도난)와 reserve(여벌) 배열에 모두 포함된 학생은 빌려줄 수 없으므로 미리 제거해야 한다.

정렬: 앞 번호부터 순차적으로 처리해야 최적의 해를 구할 수 있으므로 배열을 오름차순 정렬한다.

빌리는 순서: 내 앞 번호(i-1)에게 빌릴 수 있으면 먼저 빌리고, 없으면 뒷 번호(i+1)에게 빌린다.

이유: 앞 번호의 여벌 체육복은 내가 안 쓰면 그냥 버려지지만, 뒷 번호의 여벌은 내 뒤의 친구가 쓸 수도 있기 때문이다.

방법 1: 배열(카운팅) 활용 (추천 👍)학생 수가 적으므로( $N \le 30$ ), 학생들의 체육복 개수를 관리하는 배열을 만들어 직관적으로 해결한다.

모든 학생의 기본 체육복 개수를 1로 설정.
lost는 -1, reserve는 +1 연산 수행.
체육복이 0개인 학생을 찾아 앞/뒤 학생이 2개인지 확인 후 대여.

방법 2: HashSet 활용학생 수가 많거나 번호가 클 때 유용한 방법. Set의 빠른 검색 속도( $O(1)$ )를 활용한다.

reserve를 Set에 담는다.
lost를 순회하며 교집합(여벌 있는데 도난당함)을 먼저 제거한다.
남은 lost를 순회하며 Set에 앞/뒤 번호가 있는지 확인한다.

코드 1: 배열 이용

import java.util.*;

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

        int[] arr = new int[n+1];
        Arrays.fill(arr, 1);
        // 1 2 3 4 5
        // 2 0 2 0 2
        for(int idx : lost) {
            arr[idx] -= 1;
        }
        for(int idx : reserve) {
            arr[idx] += 1;
        }

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


        return answer;
    }
}

코드 2: HashSet을 이용

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        HashSet<Integer> resSet = new HashSet<>();
        
        for(int num : reserve) {
            resSet.add(num);
        }
        
        ArrayList<Integer> al = new ArrayList<>();
        for(int num : lost) {
            if(resSet.contains(num)) {
                resSet.remove(num);
            }
            else {
                al.add(num);
            }
        }
        
        for(int num : al) {
            if(resSet.contains(num-1)) {
                resSet.remove(num-1);
            }
            else if(resSet.contains(num+1)) {
                resSet.remove(num+1);
            }
            else {
                answer--;
            }
        }
        
        
        return answer;
    }
}

느낀점

그리디의 핵심은 순서: 단순히 "빌릴 수 있으면 빌린다"가 아니라, "앞사람 것을 먼저 확인하고 없으면 뒷사람 것을 본다"는 우선순위가 정답을 가르는 열쇠였다.
예외 처리의 중요성: 문제 설명에 있는 "여벌 체육복을 가져온 학생이 도난당했을 수 있다"는 문장을 대충 읽었다가 로직을 전부 다시 짰다. 문제를 꼼꼼히 읽자!
자료구조(Set)를 쓰는 것도 멋지지만, $N$ 이 작을 때는 배열을 활용한 직관적인 풀이가 더 실수할 확률이 적고 빠를 수 있다는 것을 배웠다.