[프로그래머스] 체육복(Greedy, Java, Lv1, 사고력)

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

코딩테스트 연습 - 체육복

 

## 문제접근

---

체육복을 최대한 많은 학생들에게 나눠주려고 한다. 어떻게 나눠줘야 할까? 여벌이 있는 체육복들을 탐색하면서, 앞이나 뒤 혹은 자신이 체육복을 잃어버린 목록에 포함된다면 제공하면 된다.

 

 

 

하지만, 앞이나 뒤 혹은 자신을 매번 선택해야 하는데, 어떻게 선택하는것이 가장 현명할까? 체육복 여벌이 있는 사람이 번호 순서대로 체육복을 임의로 나눠준다고 생각해보자. 낮은 번호부터 나눠줘야 생략되는 인원없이 최대한 많이 체육복을 가질 수 있다.

 

 

 

체육복을 나눠줄 때, 앞번호를 건너뛰면 앞번호 사람은 영영 체육복을 받을 수 없게 된다. 왜냐면, 체육복 여벌을 가진 사람 번호 순서대로 체육복을 나눠주고 있기 때문이다. 따라서, 앞번호를 뒷번호보다 먼저 생각해야 한다. 그래야, 최대한 많이 체육복을 나눠 가질 수 있다.

 

 

 

문제의 조건에서, 자신도 체육복을 도난당했다면 여벌 체육복을 나눠줄 수 없다는 점도 조건에 고려되어야 한다. 따라서, 체육복을 나눠주는 인원들은 고려해야할 순서는, 자기자신, 앞번호, 뒷번호 이렇게 3가지가 된다.

 

 

 

위의 조건에 맞게 코드를 작성하면 된다. 그리디는 항상 어떤 순간에 선택을 내려야 하며, 어떤 순간에 선택을 내릴 때 최적을 보장하기 위해서, 정렬과 같은 방법도 함께 고려되어야 하는 경우가 많다.

 

 

## 해설코드

---

import java.util.*;
 
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        HashSet<Integer> hs = new HashSet<>();
        for(int l : lost) hs.add(l);
        Arrays.sort(reserve);
        
        for(int i = 0; i < reserve.length; i++){
            int num = reserve[i];
            
            if(hs.contains(num)){
                hs.remove(num);
            }else if(hs.contains((num - 1 + n) % n)){
                hs.remove(num - 1);
            }else if(hs.contains((num + 1) % n)){
                hs.remove(num + 1);
            }
        }
        
        return n - hs.size();
    }
}