체육복 (Java)

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

코딩테스트 연습 - 체육복

 

프로그래머스 코딩테스트 고득점 Kit 체육복 문제 풀이이다.

 

reserve 목록 내 lost 목록을 넣어 중첩 반복문으로 비교해서 풀었다.

초반엔 비교적 쉽게 풀리는 듯 했는데 일부 테스트 케이스를 실패했고 실패 원인은 아래와 같았다.

 

- 12, 13, 18 테스트 케이스 실패

reserve 목록과 lost 목록은 정렬되어있지 않을 수 있어 도난 당한 사람의 앞, 뒤 모두 여벌옷이 있을 때 뒷 사람에게 먼저 빌려주는 경우가 생겨 최적의 방법을 찾지 못하는 경우가 생긴다. 각 목록은 정렬해주어야 한다.

 

- 5, 12 테스트 케이스 실패

도난 당한 사람이 여벌 옷이 있을 때는 남은 체육복이 하나로 본인이 입어야 해서 다른 사람에게 빌려주지 못한다. 단순히 입을 수 있는 사람의 수만 늘리는게 아니라 본인이 입어야 하는데 남에게 먼저 빌려주게 되는 경우가 생기지 않도록 처리해주어야 한다.

n: 3 / lost: [1, 2] / reserve: [2, 3] 의 경우를 생각해보면 정답은 2고, 1에게 2가 빌려주게 되면 안 되기 때문에 removeAll()로 두 목록을 비교해 이런 경우는 리스트에서 미리 지워주어야 한다.

 

 

import java.util.stream.Collectors;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // int[] to List<Integer>
        List<Integer> lostList = Arrays.stream(lost).boxed().collect(Collectors.toList());
        List<Integer> reserveList = Arrays.stream(reserve).boxed().collect(Collectors.toList());
        
        // 도난 당한 사람이 여벌 옷이 있을 때는 무조건 본인이 가져야 함(남에게 빌려줄 수 없음)
        // lost가 [1, 2]일 때 reserve가 [2, 3]이면 2번이 1번에게 먼저 옷을 빌려주게 되므로 두 리스트 간 중복 제거
        List<Integer> targetLostList = new ArrayList<>(lostList);
        List<Integer> targetReserveList = new ArrayList<>(reserveList);
        targetLostList.removeAll(reserveList);
        targetReserveList.removeAll(lostList);
        
        // 전체 인원 수에서 도난 당한 수 제외, 도난 당한 사람이 여벌 옷이 있는 경우 제외
        int answer = n - lost.length + (lostList.size() - targetLostList.size());

        // 목록이 정렬되어 있어야 순차적으로 비교 가능
        Collections.sort(targetLostList);
        Collections.sort(targetReserveList);
        
        // 여벌 옷 있는 사람 중 빌려줄 수 있는 사람 찾기
        for (int i = 0; i < targetReserveList.size(); i++) {
            int prev = targetReserveList.get(i) - 1;    // 이전 번호
            int next = targetReserveList.get(i) + 1;    // 이후 번호
            for (int j = 0; j < targetLostList.size(); j++) {
                int temp = targetLostList.get(j);
                if (temp == prev || temp == next) {
                    targetLostList.remove(j);   // 이미 빌려준 경우 목록에서 제외
                    answer++;
                    break;
                } 
            }
        }
        return answer;
    }
}