[programmers] 체육복

체육복

x
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
​
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
​
제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

조금 잘못 생각했다고 이렇게 문제를 헤맬 수 있나..!

도둑놈이 잘못했다. 아무튼 도둑놈이 문제야.. 아무튼 맞음 ㅠ

 

사실 문제 자체는 간단하다. 전형적인 탐욕 알고리즘 문제.

도둑놈은 참 양심적이게도 한 명당 하나의 체육복만 훔쳐간다. 그리고 내 옷이 도난당했을 때 여벌옷이 있는 친구가 있어도 그 친구가 내 앞번이나 뒷번이어야 체육복을 빌릴 수 있다. 우리 반은 학번이 이름순이었는데.

내가 왜 헤맸냐? 내가 처음 푼 로직을 한번 보자.

 

x
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
​
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
​
        List<Integer> resList = Arrays.stream(reserve).boxed().collect(Collectors.toList());
​
        for (int lostOne : lost) {
            if (resList.contains(lostOne - 1)) {
                resList.remove(new Integer(lostOne - 1));
                answer++;
            } else if (resList.contains(lostOne)) {
                resList.remove(new Integer(lostOne));
                answer++;
            } else if (resList.contains(lostOne + 1)) {
                resList.remove(new Integer(lostOne + 1));
                answer++;
            }
        }
        return answer;
    }
}

 

뭐가 문제일까?

그렇다. 나는 그냥 안일하게 앞번의 친구거를 먼저 체크하면 될 거라고 생각했다.

내 체육복이 여벌이 있는 상태에서 도난을 당하면 그냥 내거 입으면 되는데, 이걸 지켜주지 않아서 계속 한 케이스가 틀렸던 것이다. ㅠ

 

그래서 같은 값인 지를 먼저 체크해서 제외를 시켜주고 시작했다.

 

xxxxxxxxxx
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
​
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
​
        List<Integer> resList = Arrays.stream(reserve).boxed().collect(Collectors.toList());
        List<Integer> lostList = Arrays.stream(lost).boxed().collect(Collectors.toList());
​
        for (int i = 0; i < lostList.size(); i++) {
            if (resList.contains(lostList.get(i))) {
                resList.remove(new Integer(lostList.get(i)));
                lostList.set(i, -1);
                answer++;
            }
        }
​
        for (int lostOne : lostList) {
            if (resList.contains(lostOne - 1)) {
                resList.remove(new Integer(lostOne - 1));
                answer++;
            } else if (resList.contains(lostOne + 1)) {
                resList.remove(new Integer(lostOne + 1));
                answer++;
            }
        }
​
        return answer;
    }
}

 

for문 하나 더 넣어서 중복값 체크/제외를 해주었더니 드디어 정확도 100%가 나왔다.

문제의 작은 힌트 하나 놓치지 마세요.. (네..)