[프로그래머스][Java] - 체육복 / 탐욕법(Greedy)

문제

풀이

요약하자면

• n: 전체 인원 수
• lost: 체육복을 도난당한 학생들의 번호
• reserve: 여별의 체육복을 가지고 온 학생들의 번호

를 인자로 받아서 최대한 많은 학생들이 체육복을 나눠서 입을 수 있는 경우를 구하는 문제이다.

해결 방법은 각 학생이 가질 수 있는 체육복의 수는 0, 1, 2이므로 배열로 정리하여,
해당 배열의 원소가 2이고 조건에 따라 앞이나 뒤의 원소가 0일 경우,
앞 원소를 우선으로 주는 것으로 설정하여 양 옆에 수를 나누어주며 해결했다.
예를 들어 n = 5, lost = [2, 4], reserve = [1, 3, 5]인 경우 수로 나열하면 20202이고,
2인 경우 자신에게서 1을 빼서 0에 1을 더해주므로 21111이 된다

코드

class Solution {
    
    public boolean contain(int[] arr, int n) {
        for (int i : arr) if(i == n) return true;
        return false;
    }
    
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            if(contain(lost, i + 1) && contain(reserve, i + 1)) {
                arr[i] = 1;
            } else if(contain(lost, i + 1)) {
                arr[i] = 0;
            } else if(contain(reserve, i + 1)) {
                arr[i] = 2;
            } else {
                arr[i] = 1;
            }
        }
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] == 2) {
                if(i != 0 && arr[i - 1] == 0) {
                    arr[i]--;
                    arr[i - 1]++;
                } else if(i != arr.length - 1 && arr[i + 1] == 0){
                    arr[i]--;
                    arr[i + 1]++;
                }
            }
        }
        for (int i : arr) if(i != 0) answer++;
        
        return answer;
    }
}

여러번 사용되는 배열 내 원소 포함 체크 로직은 contain 함수로 빼고,
총 학생수만큼 루프를 돌고 조건 체크를 하여 arr에 학생별 체육복 수를 담는다.
이때, 여벌 체육복을 가진 학생이 체육복을 도난당했을 경우도 체크해줘야 한다.
이렇게 만들어진 arr를 루프를 돌며 원소가 2인 경우 조건문 안으로 들어가는데,
첫번째 원소가 아니고 이전 원소가 0인 경우와
마지막 원소가 아니고 다음 원소가 0인 경우로 나누어,
해당 원소에서 1을 빼고 앞이나 뒤의 원소에 1을 추가한다.