[알고리즘] 프로그래머스 - 체육복 (탐욕법)

1. 문제

2. 문제 풀이

체육복을 빌릴 때 체육복이 없고, 앞에 사람이 여유분이 있다면 무조건 앞에 사람한테서 체육복을 빌린다. 만약 앞에 사람이 여유 체육복이 없고 뒤에 사람이 여유 체유복이 있으면 뒤에 사람한테 빌리도록 순서를 강제한다.

import java.util.*;

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

        return answer;
    }
}