99클럽 코테 스터디 20일차 TIL - 그리디

문제

[체육복]

풀이

• 양 옆에 있는 학생에게만 체육복을 빌려줄 수 있음
• 자신이 여분이 있었는데 잃어버렸을 경우도 고려해야함

코드

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        // check 배열 생성
        int[] students = new int[n+1];
    
        Arrays.fill(students, 1);
        Arrays.sort(reserve);
        
        // 도난했으면 -1
        for(int l : lost){
            students[l] -= 1;
        }
        
        // 여분있으면 +1
        for(int r : reserve){
            students[r] += 1;
        }
        
        for (int r : reserve) {
            int cur = r;
            int prev = r - 1;
            int next = r + 1;
           
            // 여분이 없으면 패스
            if(students[cur] < 2) continue;
            
            if (prev > 0 && students[prev] == 0) {
                students[prev] += 1; 
                students[cur] -= 1; 
            } else if (next <= n && students[next] == 0) {
                students[next] += 1; 
                students[cur] -= 1; 
            }   
        }
        
        return count(students);
    }
    
    
    public static int count(int[] array) {
        int count = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i] > 0) {
                count++;
            }
        }
        return count;
    }
}

정리

• 반례를 생각 못 해서 오래 걸림
• reserve를 내림차순으로 해야하는데 이거를 생각 못 해서...