[프로그래머스] 42862 체육복(Lv.1) - 그리디(Greedy)

문제

코드

• 풀이 방법
  1. lost 학생이 reserve에도 있는지 확인(있다면 빌릴 필요 없음)
  2. 1에 해당하지 않다면 앞 뒤로 reserve 학생이 있는지 확인 후 있다면 빌리기

시도 1 - X

테스트 케이스를 실행해보면 두 개의 케이스에서 실패가 뜬다. 아무리 생각해도 모르겠어서 chatGPT의 힘을 빌렸다..

import java.util.*;
class Solution {
    // n: 전체 학생 수, lost[]: 도난당한 학생들의 번호, reserve[]: 여벌 체육복 있는 학생들의 번호
    public int solution(int n, int[] lost, int[] reserve) {
        int result = n - lost.length;

        // 여분이 있으면서 도난 당한 학생 처리
        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;
                    result += 1;
                    break;
                }
            }
        }

        // 여분이 없고 도난 당한 학생 처리
        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 (lost[i] -1 == reserve[j] || lost[i] +1 == reserve[j]) {
                    reserve[j] = -1;
                    result += 1;
                    break;
                }
            }
        }
        return result;
    }
}

시도 2 - O

만약 lost = [4, 2], reserve = [3, 5]인 경우, 정렬 없이는 2번 학생이 3번 학생에게서 체육복을 빌리지 못한다.
이 문제 뿐만 아니라 회의실 배정 문제, 최소 비용 동전 문제 등 다양한 그리디 문제에서 정렬은 매우 중요한 부분이다. 정렬을 해야 각 단계에서 최적의 선택을 할 수 있기 때문이다. 앞으로 그리디 문제를 풀 때 정렬을 항상 염두에 두고 풀자.

import java.util.*;
class Solution {
    // n: 전체 학생 수, lost[]: 도난당한 학생들의 번호, reserve[]: 여벌 체육복 있는 학생들의 번호
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);
        int result = n - lost.length;

        // 여분이 있으면서 도난 당한 학생 처리
        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;
                    result += 1;
                    break;
                }
            }
        }

        // 여분이 없고 도난 당한 학생 처리
        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 (lost[i] -1 == reserve[j] || lost[i] +1 == reserve[j]) {
                    reserve[j] = -1;
                    result += 1;
                    break;
                }
            }
        }
        return result;
    }
}