[프로그래머스] 탐욕법 - 구명보트

 

배열 하나를 만들어서, lost 배열에 인덱스 값은 1씩 빼주고, reserve 배열에 인덱스 값들은 1씩 더해준다. 이 기초 배열을 토대로 반복실행하여 해당 인덱스가 체육복이 없는 상황이면 인덱스가 마지막 학생이 아닌 경우, 뒤에 학생의 옷이 두 벌일 때 빌리고, 첫번째 학생이 아닌 경우, 앞에 학생이 옷이 두 벌일 때 빌리는 방식으로 답을 구해가면 된다.

 

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int [] ary = new int [n];
        
        for(int i=0;i<lost.length;i++){
            ary[lost[i]-1]--;
        }
        
        for(int i=0;i<reserve.length;i++){
            ary[reserve[i]-1]++;
        }
        
        for(int i=0;i<n;i++){
            if(ary[i]<0){
                if (i != n - 1 && ary[i + 1] > 0) {
                    ary[i]++;
                    ary[i + 1]--;
                } else if (i != 0 && ary[i - 1] > 0) {
                    ary[i]++;
                    ary[i - 1]--;
                }
            }
        }       
        
        for(int i=0;i<n;i++){
            if(ary[i] >= 0){
                answer++;
            }
        }
        return answer;
    }
}