코딩테스트#002 체육복 (탐욕법)

A Kind Dev·2022년 6월 19일

코딩테스트

목록 보기

2/19

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.

학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

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

제한사항

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

예제 #1

n lost reserve return
5 [2, 4][1, 3, 5] 5
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

나의 풀이

import java.util.Arrays;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        
        // 1. 수업을 들을 수 있는 학생 수 초기화 (전체 학생 - 체육복을 도난당한 학생)
        int answer = n - lost.length;
       
       // 2. 배열 오름차순으로 정렬
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        // 3. 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우
        // 수업을 들을 수 있는 학생 수에 추가
        // 도난 당한 학생, 여벌 체육복 학생 목록에서 비교 불가하도록 의미없는 수 100 셋팅
        for (int i = 0; i < reserve.length; i++) {
            for (int j = 0; j < lost.length; j++) {
                if (reserve[i] == lost[j]) {
                    answer++;
                    reserve[i] = 100;
                    lost[j] = 100;
                    break;	// 더 비교할 필요가 없으므로
                }
            }
        }
        
        // 4. 체육복을 빌려줄 수 있는 경우 계산
        // 도난 당한 학생, 여벌 체육복 학생 목록에서 100 이 아닌 경우 중
        // 도난 당한 학생 = 여벌 체육복 학생 +1 or 도난 당한 학생 = 여벌 체육복 학생 -1
        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] != 100 && reserve[j] != 100) {
                    if (lost[i] == reserve[j] + 1 || lost[i] == reserve[j] - 1) {
                        answer++;
                        reserve[j] = 100; // 한 번 빌려준 학생은 다시 빌려줄 수 없도록
                        break;  // 더 빌릴 필요가 없으므로
                    }
                }
            } 
        }
        
        return answer;
    }
}

풀이포인트

탐욕법이란?

탐욕법(Greedy Algorithm)은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘으로, 동적 프로그래밍을 대체하는 것은 아니고 보완하는 개념.

미래를 생각하지 않고 현재 단계에서 가장 최선의 선택을 하는 기법으로, 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘.

따라서 모든 경우에 탐욕법이 통하지는 않는다. 예를들어 지금 선택하면 1개의 마시멜로를 받고, 1분 기다렸다 선택하면 2개의 마시멜로를 받는 문제에서는, 그리디 알고리즘을 사용하면 항상 마시멜로를 1개밖에 받지 못한다. 지금 당장 최선의 선택으로 마시멜로 1개를 받지만, 결과적으로는 1분 기다렸다가 2개 받는 게 최선.

이처럼 탐욕법은 순간마다 최선의 결정이 최선의 선택이 될 수는 없지만, 계산 속도가 빠르기 때문에 탐욕법 적용이 가능한 몇몇 문제에서는 좋은 대안.

탐욕법이 적용되는 문제의 조건

탐욕스러운 선택 조건
탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. 탐욕법이 항상 최선의 선택을 보장하지는 않으므로, 탐욕법을 사용했을 때 반드시 최적의 해를 도출할 수 있는지를 생각해야 한다.
최적 부분 구조 조건
문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이어야 한다. 하나의 문제 안에 여러 단계가 존재하고, 각 단계마다 최적의 해가 도출되어야 한다. 이를 위해서는 각 값이 다른 값에 영향을 주어서는 안된다.

체육복 문제의 풀이 포인트

위 문제가 탐욕법 적용이 가능한 것은, 문제를 푸는 과정에서 모든 경우의 수를 체크하게 되며, 여분 체육복을 가져온 학생을 체크하는 단계와 체육복을 빌려줄 수 있는 경우를 계산하는 단계가 서로 독립적인 동시에 최적의 해가 보장되기 때문이다.
배열의 오름차순 정렬
체육복을 도난당한 학생의 배열과 여벌 체육복을 가져온 학생의 배열을 오름차순 정렬하고 시작해야 한다. 그렇지 않으면 테스트 케이스 13, 18번에서 오류 발생!
테스트 케이스 13번은 n=5 lost=[4,2] reserve=[3,5]. 바른 return 값은 5인데, 정렬하지 않을 경우 4번학생은 3번에게 빌려주게 되고, 2번 학생은 여분 체육복을 받지 못해 수업이 가능한 학생수가 4명이 된다.
나의 풀이는 배열을 오름차순으로 순회하기 때문에 오름차순으로 정렬하였고, 반대의 경우에는 내림차순 정렬을 하면 된다.
학생 수는 30명 이하이므로 의미없는 수는 31 보다 큰 수를 셋팅한다. (31 - 1 은 30이므로 31 보다 커야 한다.)
한 번 빌려준 학생은 다시 빌려줄 수 없음을 반드시 체크한다. 그렇지 않으면 7번 테스트 케이스를 통과하지 못한다.