# Level 1 - 탐욕법-체육복

[문제]

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.

 

학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

 

[내 풀이]

총 두번의 반복문으로 처리했고 수업을 들을 수 없는 학생을 제외하는 방식을 사용했다.

첫번째 반복문은 잃어버린 학생들 중 여벌 옷을 가져온 학생이 도난 당한 경우를 제외하였고,

두번째 반복문은 잃어버린 학생들 중 여벌 옷을 빌릴 수 있는 경우를 제외하였다.

 

문제는 해결하였지만 코드가 마음에 들지는 않는다.

 

문제 하나, int[] -> Collection 으로 변환하는 과정을 stream()을 사용했는데 깔끔하진 않아 보인다. 더 간단한 방법이 없을까?

 

문제 둘, 필요 이상?의 인터페이스와 Collection을 사용했다.

Set, Arrays, Iterator, stream 까지. 반면 아래 다른 사람 코드는 for문 만으로 문제를 해결하였다.

import java.util.stream.Collectors;
import java.util.Arrays;
import java.util.Set;
import java.util.Iterator;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> reserveSet = Arrays.stream(reserve).boxed().collect(Collectors.toSet());
        Set<Integer> lostSet = Arrays.stream(lost).boxed().collect(Collectors.toSet());

        // 잃어버린 사람과 여벌 옷 있는 사람이 같은 사람이라면 두 개의 리스트에서 모두 제외
        Iterator<Integer> itr = lostSet.iterator();
        while (itr.hasNext()){
            Integer lostMan = itr.next();
            if (reserveSet.contains(lostMan)){
                itr.remove();
                reserveSet.remove(lostMan);
            }
        }

        // 잃어버린 사람 리스트에서 여벌 옷이 있는 사람(앞뒤번호) 제외
        Iterator<Integer> itr1 = lostSet.iterator();
        while (itr1.hasNext()){
            Integer lostMan = itr1.next();

            int before = Math.max(lostMan - 1, 1);
            int after = Math.min(lostMan + 1, n);

            if (reserveSet.contains(before)){
                itr1.remove();
                reserveSet.remove(before);
            } else if (reserveSet.contains(after)){
                itr1.remove();
                reserveSet.remove(after);
            }
        }

        return n - lostSet.size();
    }
}

 

[다른 사람 풀이 참고]

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;
    }
}

 

<문제 출처>

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

코딩테스트 연습 - 체육복