Lv. 1 체육복

프로그래머스 _Lv. 1 체육복

문제링크

일부 학생이 체육복을 도난당해지만, 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 한다.
그러나, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다. 체육복을 입은 학생 수를 구해라

예시

• 학생의 수: 5명
• 여분의 체육복이 있는 학생 번호: 1,3,5
• 체육복을 도난 당한 학생 번호 : 2, 4
  1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

경우의 수

• 1번 케이스
  학생의 수 : 4
  여분의 체육복이 있는 학생 번호: [2, 3]
  체육복을 도난 당한 학생 번호 : [3, 4]
  결과 : 3
• 2번 케이스
  학생의 수 : 5
  여분의 체육복이 있는 학생 번호: [2, 4]
  체육복을 도난 당한 학생 번호 : [1, 3, 5]
  결과 : 3
• 3번 케이스
  학생의 수 : 5
  여분의 체육복이 있는 학생 번호: [2, 4]
  체육복을 도난 당한 학생 번호 : [3]
  결과 : 3

---

작성 조건

1. 탐욕법(Greedy) 문제
2. 번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있음
3. 체육수업을 들을 수 있는 학생의 최댓값 구함
4. 여분의 체육복이 있는 학생도 체육복을 도난 받을 수 있음
   즉, 여분의 체육복이 있는 학생 도난 시 체육복 1벌로 생각
5. 오름차순 정렬을 한 후 비교 -> 자신의 번호 앞뒤번호에게 빌려줄 수 있기 때문에 코드가 좀 더 효율성이 높아짐

코드

import java.util.Arrays;
class Solution {
    public int solution(int n, int[] lost, int[] reserver) {
        // 모든 학생 수에 체육복의 도난 당한 학생 수를 뺌 
        // 즉 answer은 체육에 참여할 수 있는 학생의 수 이미로 초기 설정 
        int answer = n - lost.length;
        //도난 당한 학생 번호 오름차순
        Arrays.sort(lost);
        //여분이 있는 학생 번호 오름차순 
        Arrays.sort(reserver);
        
        //여분의 체육복이 있지만 도난 당한 학생 구하기 
        for(int i = 0; i < reserver.length; i++){ //여분 학생 수 
            for(int j = 0; j < lost.length; j++){ //잃어버린 학생 수 
                if(reserver[i] == lost[j]){ //여분과 잃은 학생에 둘 다 포함되면 ?
                    //도난을 당했지만 여분 하나가 더 있었으므로 체육을 할 수 있어 answer을 증가시켜준다.
                    answer++;
                    //여분의 체육복을 도난 당했으므로 -1해서 여분 체육복이 없도록 체크해준다. 즉, reserver 여분의 체육복이 있는 학생 배열의 자신의 방에 -1을 체크해줌 
                    reserver[i] = -1;
                    //여분의 체육복을 도난당했지만 체육복이 있는 경우이므로 체육복이 있으므로 체크해준다. 즉 도난 당한 학생 번호의 자신의 방에 -1체크해줌 
                    lost[j] = -1;
                    break;
                } 
            }
        }
        
        //여분의 체육복 있는 학생수
        for(int i = 0; i < reserver.length; i++){ //여분 O
            for(int j = 0; j < lost.length; j++){ //도난 O
                //여분있는 학생의 앞 또는 뒤에 번호인지 확인 
                if(reserver[i] == lost[j]-1 || reserver[i] == lost[j]+ 1){
                    //체육복을 빌린 경우 lost[j]를 -1로 변경해줌 즉 대여 한 것을 체크 해줌 
                    lost[j] = -1;
                    reserver[i] = -1;
                    answer++; //체육복을 빌렸으므로 체육할 수 있는 학생의 수 추가 
                    break;
                }
            }
        }
        return answer;
    }
}

코드 해설
1. import java.util.Arrays;
오름차순 정렬 Arrays.sort()를 사용하기 위해 작성함
2. Arrays.sort(lost); Arrays.sort(reserver);
반복을 볼 때 더 효율성 있게 작성하기 위해서 오름차순 정렬을 함
3. if(reserver[i] == lost[j])
여분의 체육복이 있지만, 도난 당한 학생인지 아닌지 조건을 통해 체크 해줌. 즉, 여분이 있지만 도난 당한 경우는 여분 체육복이 없는 경우로 생각해야 하고 자신은 체육에 참여할 수 있으므로 answer++ 증가해주고, 여분체육복과 도난학생의 자신의 방을 -1로 없음으로 체크해줌
4. if(reserver[i] == lost[j]-1 || reserver[i] == lost[j]+ 1)
여분있는 학생의 앞 또는 뒤에 번호인지 확인