[Programmers] 체육복 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.*;

class Solution {
    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]) {
                    reserve[j] = -1;    // 대여불가로 변경
                    lost[i] = -1;       // 체육복은 하나씩만 도난 당하므로 본인 것은 있음
                    answer++;
                    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]) {
                    reserve[j] = -1;    // 대여불가로 변경
                    answer++;
                    break;
                }
            }
        }
        
        return answer;
    }
}

📄 해설

• 그리디 알고리즘 문제로, 아래 두가지 경우에만 도난 당한 학생이 체육복을 가질 수 있음
  1. 여벌 체육복을 가져온 학생이 도난당한 경우
  2. 도난당한 학생에게 빌려줄 수 있는 경우
• answer 의 초기값을 전체 학생 수 - 도난당한 학생 수 로 설정하고, 위 두 경우에 answer 의 값을 1씩 증가시키면 해결