[프로그래머스 (Java)] 체육복

https://programmers.co.kr/learn/courses/30/lessons/42862?language=java 

코딩테스트 연습 - 체육복

Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다.

해당 문제에서는 m 개의 reserve 가 주어졌을때 최적해를 구하고 m+1 개의 reserve 가 주어졌을때 최적해를 구해서 최종적으로 n 개의 reserve 가 주어졌을때 최적해를 구함으로서 Greedy 를 이용합니다.

최적해를 구할때 여분의 체육복을 가지고 있는 사람은
1. 최우선적으로 자신의 체육복이 도난당했는지 확인
2. 이후 자신의 앞사람이 도난당했는지 확인

3. 마지막으로 자신의 뒷사람이 도난당했는지 확인

하면서 자신의 여분의 체육복을 빌려줍니다. 부분적으로 자신의 앞사람을 우선적으로 빌려주는 것이 전체적으로 최적해를 구할 수 있다는 판단을 하는것이 중요합니다.

 

solution 1

public class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> lostSet = new HashSet<>();
        List<Integer> reserveList = new ArrayList<>();
        for (int l : lost) {
            lostSet.add(l);
        }

        for (int r : reserve) {
            if (lostSet.contains(r)) {
                lostSet.remove(r);
            } else {
                reserveList.add(r);
            }
        }

        for (Integer r : reserveList) {
            if (lostSet.contains(r - 1)) {
                lostSet.remove(r - 1);
            } else lostSet.remove(r + 1);
        }

        int answer = n - lostSet.size();
        return answer;
    }
}

 

solution2 

public class Solution {    
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;

        for (int l : lost)
            people[l - 1]--;
        for (int r : reserve)
            people[r - 1]++;

        for (int i = 0; i < people.length; i++) {
            if (people[i] == -1) {
                if (i - 1 >= 0 && people[i - 1] == 1) {
                    people[i]++;
                    people[i - 1]--;
                } else if (i + 1 < people.length && people[i + 1] == 1) {
                    people[i]++;
                    people[i + 1]--;
                } else
                    answer--;
            }
        }
        return answer;
    }
}