[Java/자바] 프로그래머스 - 체육복/Greedy(탐욕법) 알고리즘

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다.

다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.

학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다.

체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때,

체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

입출력 예

n	lost	reservere	turn
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

---

Solution.java

import java.util.Arrays;

    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;

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

        // 여벌 체육복을 가져온 학생이 도난당한 경우
        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] == reserve[j]) {
                    answer++;
                    lost[i] = -1;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        
        // 도난당한 학생에게 체육복 빌려주는 경우
        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if ((lost[i] - 1 == reserve[j]) || (lost[i] + 1 == reserve[j])) {
                    answer++;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        return answer;
    }

---

풀이

Greedy(탐욕법)이란?

현재 상황에서 가장 좋은 것을 고르는 알고리즘입니다.

현재 상황에서 가장 좋은 것을 고른다는 것은 어떠한 문제가 여러 단계로 나뉘어

차례로 알고리즘이 이어지는 경우, 그 단계마다 가장 좋은 선택을 한다는 것을 의미.

 

이 문제를 푸는데 눈여겨봐야할 부분은 제한사항의 "여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다."입니다.

여벌 체육복을 가져온 학생이 도난당한 경우를 구해야 모든 테스트 케이스가 통과하기 때문에

다른 문제와 다르게 함정이 숨어있는 문제입니다.

 

여기서 체육복을 빌려줬을 경우 배열의 값을 -1로 변경하였는데, 배열은 값 삭제를 할 수 없어 -1로 변경했습니다.

만약 배열 값을 0으로 변경했을 경우 lost[i] + 1에서 if문을 탈 가능성이 있기 때문에 -1로 변경하는 것이 안전합니다.

아니라면 StringBuffer 클래스를 사용해도 됩니다.

 

그리고 체육복을 빌려줬을 경우 해당 값을 -1로 변경 후 break; 처리를 하였는데

break 처리를 하지 않는다면 다음과 같은 경우가 발생합니다.

체육복을 도난 당한 학생 배열이 [2, 4]이고, 여벌 체육복을 가져온 학생의 배열이 [1, 3, 5]일 때

1이 2에게 체육복을 빌려주면 answer의 값은 4,

3이 2한테 빌려주고 4한테도 빌려주면 answer의 값은 5,

5가 4한테 빌려주면 answer의 값은 6으로 기대값 5와 다른 결과가 나오게 됩니다. 

위 경우에서 오류가 난 이유는 이미 3이 4한테 체육복을 빌려줬는데 5가 또 4한테 체육복을 빌려줬기에 오류가 발생하였습니다.

그래서 break 처리가 필요한데

일반 for문에서 break처리시 for문을 빠져나오지만,

이중 for문에서 break처리를 하면 현재 위치한 가장 안쪽의(j) 반복문에서 빠져나오고 다시 제일 바깥쪽의 반복문(i)을 실행하게 됩니다.

즉 i가 0이고, j가 0일 때 2번 학생은 이미 체육복을 받았기 때문에 더 받을 필요가 없어 다음 학생으로 넘어가는 것입니다.