[프로그래머스] 체육복

프로그래머스 <체육복>

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

코딩테스트 연습 - 체육복

---

<체육복>

전체 학생의 수와 체육복을 도난당한 학생의 list, 여분의 체육복을 가져온 학생의 list를 알고 있을 때,

체육 수업을 들을 수 있는 학생의 최대 수를 알아내라.

 

도난당한 학생은 자신의 학생 번호 +1, -1 학생이 여분의 체육복을 가져왔을 경우 빌릴 수 있다

체육 수업은 꼭 체육복을 입어야 수강할 수 있다.

 

여분의 체육복을 가져왔고 체육복을 도난당했을 경우에는 자신이 여분의 체육복을 입어야 한다.

---

문제 해결

이 문제는 탐욕적으로 해결하면 된다.

도난당한 학생의 +1, -1 학생이 여분의 체육복을 가져왔을 경우, 체육복을 빌려준다.

이때 -1 학생의 체육복을 우선으로 빌린다. (왜냐면 도난당한 학생들을 학생번호가 작은 수부터 보기 때문에 -1 학생의 체육복을 우선으로 빌려야 현재 +1 학생의 체육복이 현재 도난당한 학생 번호말고 다음 도난당한 학생 번호의 -1 학생일 수도 있기 때문에)

 

이를 위해서는 준비?가 필요하다.

lost와 reserve가 학생 번호의 list로 들어오기 때문에 처리가 필요하다.

전체 학생의 수가 최대 30까지 밖에 되지 않기 때문에 re_bool의 배열을 만들어서 여분의 체육복을 가진 학생은 true 값을 갖도록 하였다.

또한 여분의 체육복을 가져오고 도난을 당할 수도 있기 때문에 real_lost를 만들었다.

real_lost는 LinkedList로 여분의 체육복을 가져왔고 도난을 당한 학생을 뺀 진짜로 체육복이 없는 학생을 가지고 있다.

 

자신의 체육복을 입고 체육 수업에 참여할 수 있는 학생의 수는 전체 학생의 수(n) - real_lost.size()이다.

 

준비를 끝낸 후에는 

real_lost의 값을 하나씩 보면서 -1 학생의 re_bool의 값이 true라면 체육복을 빌릴 수 있기 때문에 answer에 +1을 해주고 해당 re_bool의 값은 false로 한다. 이미 체육복을 빌렸기 때문에 +1 학생은 볼 필요가 없다. -> continue

-1 학생의 re_bool의 값이 false인 경우,

+1 학생의 re_bool의 값이 true라면 체육복을 빌릴 수 있기 때문에 answer +1을 해주고 해당 re_bool의 값은 false로 하면 된다.

 

이때 -1, +1 학생의 번호가 1 <= 학생 번호 <= n 임을 잊지 말아야 한다.

---

코드

import java.util.Arrays;
import java.util.LinkedList;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        boolean[] re_bool = new boolean[n+1];
        LinkedList<Integer> real_lost = new LinkedList<>();
        
        for(int i = 0; i < n+1; i++){
            re_bool[i] = false;
        }
        for(int i = 0 ; i < reserve.length; i++){
            re_bool[reserve[i]] = true;
        }
        Arrays.sort(lost);
        for(int i = 0 ; i < lost.length; i++){
            if(re_bool[lost[i]]){
                re_bool[lost[i]] = false;
            }else{
                real_lost.add(lost[i]);
            }
        }
        int len = real_lost.size();
        answer = n - len;
        for(int i = 0; i < len; i++){
            int plus = real_lost.get(i) + 1;
            int minus = real_lost.get(i) - 1;
            if(minus > 0){
                if(re_bool[minus]){
                    re_bool[minus] = false;
                    answer++;
                    continue;
                }
            }
            if(plus < n+1){
                if(re_bool[plus]){
                    re_bool[plus] = false;
                    answer++;
                }
            }
            
        }
        return answer;
    }
}

---

결과

---