프로그래머스 - 42862번: 체육복 [Java]

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        boolean[] check = new boolean[n + 1];
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        for(int l : lost) {
            for(int r : reserve) {
                if(l == r) {
                    check[r] = true;
                    answer++;
                    break;
                }
            }
        }
        
        for(int l : lost) {
            if(check[l]) continue;
            for(int r : reserve) {
                if(!check[r] &&(r - 1 == l || r + 1 == l)){
                    check[r] = true;
                    answer++;
                    break;
                }
            }
        }
        return answer;
    }
}

2. 설명

int answer = n - lost.length;
boolean[] check = new boolean[n + 1];
Arrays.sort(lost);
Arrays.sort(reserve);

우선 총학생의 수 - 체육복을 잃어버린 학생의 수를 통해서 체육복을 1개만 가진 학생을 구합니다. 그리고 check 배열을 통해서 여분의 체육복을 가지고 있는 학생이 잃어버리거나 이미 나누어줬음을 확인합니다. lost와 reserve를 오름차순으로 정렬을 하여 순차적으로 접근합니다.

for(int l : lost) {
    for(int r : reserve) {
        if(l == r) {
            check[r] = true;
            answer++;
            break;
        }
    }
}

반복문을 통해서 여분의 체육복을 가지고 있는 학생이 잃어버렸는지 확인합니다. 만약 잃어버렸다면 다른 학생에게 나누어 줄 수 없지만 자기 자신은 체육복을 가지고 있기에 check[r]에는 true를 answer에는 1증가를 해줍니다.

for(int l : lost) {
    if(check[l]) continue;
    for(int r : reserve) {
        if(!check[r] &&(r - 1 == l || r + 1 == l)){
            check[r] = true;
            answer++;
            break;
        }
    }
}

잃어버린 학생이 여분의 체육복을 가진 학생의 경우는 continue를 하여 넘어가며 아닌 경우 여분의 학생이 잃어버리거나 나누어준 상태라면 넘어갑니다. 아니라면 여분의 학생이 잃어버린 학생 기준으로 1보다 낮거나 높으면 체육복을 나누어 줄 수 있기에 check[r]에 true를 answer에 1증가를 하여 체육복을 나누어 주었다는 것을 표시하니다. 그리고 answer를 반환하면 문제는 해결됩니다.

3. 정리

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

위 조건을 보지 않고 문제를 해결하다가 오래 걸렸는데 문제를 자세히 읽어야겠다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges