#22 😂 체육복 with Greedy algorithm

[문제]

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

출처 : https://school.programmers.co.kr

출처 : https://school.programmers.co.kr

---

[해설]

- 풀이법은 어느정도 접근했는데 결국엔 풀지 못 했다.()

- 다른 사람의 풀이를 참고한 내용을 올린다.(내 풀이를 어디다 적어놨었는데 그게 사라졌는지 못 찾았다.)

import java.util.HashSet;
import java.util.Arrays;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        int answer = n - lost.length;
        HashSet<Integer> cheUkBok = new HashSet<Integer>();
        
        for(int i : reserve) cheUkBok.add(i);

        for(int i = 0; i < lost.length; i++) {
            if(cheUkBok.contains(lost[i])) {
                answer++;
                cheUkBok.remove(lost[i]);
                lost[i] = -1;
            }
        }

        for(int i = 0; i < lost.length; i++) {
            if(cheUkBok.contains(lost[i] - 1)) {
                answer++;
                cheUkBok.remove(lost[i] - 1);
            } else if(cheUkBok.contains(lost[i] + 1)) {
                answer++;
                cheUkBok.remove(lost[i] + 1);
            }
        }
        return answer;
    }
}

 

● Arrays.sort를 먼저 한 이유

- Greedy algorithm의 핵심은 최종 결과의 선택이 최선(최적) 일때 매 순간 선택 또한 최선(최적)이 되어야한다는 것이다.

- 매 순간의 선택 중 하나라도 최선(최적)이 아니라면 Greedy algorithm이라고 할 수 없다.

- 아래의 상황을 예로 생각해보자

n = 5
lost = [4, 2]
reserve = [3, 5]
cheUkBok = [3, 5]

- 코드 없이 단순 눈으로만 계산하면 (4번 학생은 5번 학생)에게, (2번 학생은 3번 학생)에게 체육복을 빌릴 수 있다.

- 체육복을 잃어버린 학생들이 각각 자신의 뒷번호 학생에게 빌리면 되므로 이경우 (n = 5)가 된다.

- 하지만 코드는 그런 마음의 눈이 없다.

for(int i = 0; i < lost.length; i++) {
    if(cheUkBok.contains(lost[i] - 1)) {
        answer++;
        cheUkBok.remove(lost[i] - 1);
    } else if(cheUkBok.contains(lost[i] + 1)) {
        answer++;
        cheUkBok.remove(lost[i] + 1);
    }
}

- 만약 lost 배열이 정렬된 상태가 아니라면 (i = 0)일 때 아래의 결과로 if 문을 만족하게 된다.

if(cheUkBok.contains(lost[0] - 1)) = if(cheUkBok.contains(3)) --> true
cheUkBok.remove(3);

cheUkBok = [5];

- 즉, 2번 학생이 3번 학생이 아닌 4번 학생에게 체육복을 빌리게 되는 것이다.

- 이 상태에서 (i = 1)일 때는 if 문을 아무것도 만족할 수 없게 되고 (n = 4)가 된다.

cheUkBok = [5];

if(cheUkBok.contains(lost[1] - 1)) = if(cheUkBok.contains(1)) --> false
if(cheUkBok.contains(lost[1] + 1)) = if(cheUkBok.contains(3)) --> false

- (n = 5)가 최적의 답변인데 정렬을 하지 않으면 (n = 4)가 되므로 이는 문제의 답을 만족했다고 할 수 없다.

- 이러한 연유로 Arrays.sort를 먼저 해야한다.

 

● if(cheUkBok.contains(lost[i] - 1))를 if(cheUkBok.contains(lost[i] + 1)) 보다 먼저 비교한 이유

- 이것도 Arrays.sort를 먼저 한 이유와 비슷하다.

for(int i = 0; i < lost.length; i++) {
    if(cheUkBok.contains(lost[i] - 1)) {
        answer++;
        cheUkBok.remove(lost[i] - 1);
    } else if(cheUkBok.contains(lost[i] + 1)) {
        answer++;
        cheUkBok.remove(lost[i] + 1);
    }
}

n = 6
lost = [2, 4, 6]
reserve = [1, 3, 5]
cheUkBok = [1, 3, 5]

- 위와 같은 조건이 주어졌을 때 코드 없이 단순 눈으로만 계산하면 (2번 학생은 1번 학생)에게, (4번 학생은 3번 학생)에게,

(6번 학생은 5번 학생)에게 체육복을 빌릴 수 있다.

- 따라서 (n = 6)이 된다.

- 이때 만약 아래와 같이 if(cheUkBok.contains(lost[i] + 1))를 먼저 비교했다고 해보자

for(int i = 0; i < lost.length; i++) {
    if(cheUkBok.contains(lost[i] + 1)) {
        answer++;
        cheUkBok.remove(lost[i] + 1);
    } else if(cheUkBok.contains(lost[i] - 1)) {
        answer++;
        cheUkBok.remove(lost[i] - 1);
    }
}

- 그러면 (2번 학생은 3번 학생)에게, (4번 학생은 5번 학생)에게 체육복을 빌릴 수 있지만 6번 학생은 체육복을 빌리지 못 하게 되므로 (n = 5)이 된다.

- 이러한 케이스가 있으므로 if(cheUkBok.contains(lost[i] - 1))를 먼저 비교해야한다.

 

 

cf) 아래 영상으로 Greedy algorithm을 먼저 공부했다.

https://youtu.be/hWKZ2G_OQwQ