[프로그래머스] Lv.1 : 체육복 - 자바[Java]

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

1. 풀이

2 <= n <= 30

1 <= 도난당한 학생 수, 여벌이 있는 학생 수 <= n

 

int[] students 배열을 생성하여, 각 학생의 체육복 수를 저장한다.

0: 하나의 체육복만 가지고 있는 경우

1: 여벌의 체육복을 하나 더 가지고 있는 경우

-1: 도난당해 체육복이 하나 더 필요한 경우

 

로직

1. 여벌의 체육복이 있는 경우 students[i]++

2. 도난당한 경우 students[i--]

3. 도난당한 학생들의 번호를 정렬한다.

4. 도난당한 학생들 양 옆에 여벌이 있는 학생이 있는지 확인한다. 이 때, lost를 정렬했기 때문에 번호가 작은 학생부터 잃어버린 학생들이 있는지 확인하므로, 왼쪽의 학생부터 여벌이 있는지 확인한다.

 

 

2. 코드

      

      

      

    
    

      <java />
    
import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] students = new int[n+1];
        for (int num: reserve) {
            students[num]++;
        }
        
        for (int num: lost) {
            students[num]--;
        }
        
        Arrays.sort(lost); // 번호가 작은 순대로 lost 정렬
        
        int lostStudent = 0;
        for (int num: lost) {
            if (students[num] >= 0) continue;
            
            // 양 옆 학생들 중 여벌이 있는 학생이 빌려준다.
            // 번호가 작은 학생부터 잃어버린 학생들이 있는지 확인하므로, 왼쪽의 학생부터 여벌이 있는지 확인한다.
            if (num - 1 >= 1 && students[num-1] > 0) {
                students[num-1]--;
                continue;
            }
            if (num + 1 <= n && students[num+1] > 0) {
                students[num+1]--;
                continue;
            }
            lostStudent++;
        }
        
        int answer = n - lostStudent;
        return answer;
    }
}