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

Q. 체육복

A1.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // 학생번호는 1부터 n까지 이므로 0번 인덱스를 사용하지 않음 -> n+1 크기의 배열 생성
        // clothes[]: 학생이 가진 체육복 수
        int[] clothes = new int[n + 1];
        
        // 모든 학생이 체육복을 하나씩 가지고 있다고 가정
        for (int i = 1; i <= n; i++) {
            clothes[i] = 1;
        }
        
        // lost 배열에 있는 학생은 체육복을 도난당한 거니까 체육복 수를 -1 해줌
        for (int l : lost) {
            clothes[l]--;
        }
        
        // reserve 배열에 있는 학생은 여벌 체육복이 있는 학생이니까 체육복 수를 +1 해줌
        for (int r : reserve) {
            clothes[r]++;
        }
        
        // 인접한 학생끼리만 체육복을 빌릴 수 있는데 1번부터 순차 순회하니까 왼쪽부터 확인
        // 학생 1부터 n까지 돌면서 체육복이 없는 학생이 있다면 체육복 개수가 2개인(여벌 있음) 학생이 빌려줌
        for (int i = 1; i <= n; i++) {
            if (clothes[i] == 0) { // 체육복이 없는 학생인 경우
                // 왼쪽 학생이 존재하고 여벌 체육복이 있다면 빌려줌(체육복 개수 1로 맞춰줌)
                if (i - 1 >= 1 && clothes[i - 1] == 2) {
                    clothes[i - 1] = 1;
                    clothes[i] = 1;
                }
                // 왼쪽에서 빌리지 못하고, 오른쪽 학생이 존재하고, 여벌 체육복이 있다면 빌려줌
                else if (i + 1 <= n && clothes[i + 1] == 2) {
                    clothes[i + 1] = 1;
                    clothes[i] = 1;
                }
            }
        }
        
        // 체육복을 가지고 있는 학생 수를 세서 반환
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (clothes[i] >= 1) {
                answer++;
            }
        }
        return answer;
    }
}

A2.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
    
        // boolean 배열을 사용해 flag(true, false) 활용
        // lostStudent가 true이면 그 학생은 체육복을 잃어버린 것
        // reserveStudent가 true이면 그 학생은 여벌 체육복을 가지고 있는 것
        boolean[] lostStudent = new boolean[n + 1];
        boolean[] reserveStudent = new boolean[n + 1];
        
        // lost 배열의 학생은 체육복을 잃은 거니까 lostStudent 배열에 true로 표시
        for (int l : lost) {
            lostStudent[l] = true;
        }
        
        // reserve 배열의 학생은 여벌 체육복이 있으니까 reserveStudent 배열에 true로 표시
        for (int r : reserve) {
            reserveStudent[r] = true;
        }
        
        // 도난 당했지만, 여벌도 가진 학생은 자신의 체육복으로 보충하니까 lostStudent와 reserveStudent에서 제외
        for (int i = 1; i <= n; i++) {
            if (lostStudent[i] && reserveStudent[i]) {
                lostStudent[i] = false;
                reserveStudent[i] = false;
            }
        }
        
        // 체육복이 없는 학생에 대해 여벌 체육복을 빌려줄 수 있는 지 확인
        // 왼쪽먼저 오른쪽 나중에 확인, 빌리면 false로 바꿔줌
        for (int i = 1; i <= n; i++) {
            if (lostStudent[i]) {
                if (i - 1 >= 1 && reserveStudent[i - 1]) {
                    reserveStudent[i - 1] = false;
                    lostStudent[i] = false;
                }
                else if (i + 1 <= n && reserveStudent[i + 1]) {
                    reserveStudent[i + 1] = false;
                    lostStudent[i] = false;
                }
            }
        }
        
        // 최종 체육복을 가진 학생은 lostStudent가 false인 학생
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (!lostStudent[i]) {
                answer++;
            }
        }
        return answer;
    }
}