[42862] 체육복

✔ 체육복

[프로그래머스 42862]

문제 분석하기

여벌을 가진 사람이 도난당했을 경우 빌려줄 수 없으므로 빌려줄 수 있는 배열에서 제거

그 후, 자신의 앞 뒤 사람으로부터 빌릴 수 있는지 확인

빌릴 수 있다면 빌린 후 빌린 사람가 빌려준 사람을 -1로 변경

손으로 풀어보기

1. 순차적으로 비교 탐색할 수 있도록 도난당한 학생들과 빌려줄 수 있는 학생들의 배열을 정렬
2. 여벌을 가진 사람이 도난당했을 때를 찾아 빌려줄 수 없도록 변경
   • 본인이 사용해야 하므로 다른 학생들에게 빌려줄 수 없으므로 lost와 reserve를 -1 처리
   • 이때 lost를 0으로 처리할 경우 이후 lost[i] + 1 = 1이 되어 reserve에 1이 있다면 이중으로 처리될 수 있으므로 -1로 처리
3. 체육복을 빌릴 수 있는지 비교 탐색
   • 빌릴 수 있다면 빌린 사람의 lost와 빌려준 사람의 reserve를 -1 처리
4. 체육수업을 들을 수 있는 학생의 최댓값 반환

슈도코드 작성하기

n(전체 학생의 수)
lost(체육복을 도난당한 학생들의 번호)
reserve(여벌의 체육복을 가져온 학생들의 번호)
answer(체육수업을 들을 수 있는 학생의 최댓값) = n - lost.length
lost 정렬
reserve 정렬
for(lost만큼) {
    for(reserve만큼) {
        if(여벌을 가져온 학생 중 도난 당한 학생이 있을 경우) {
            answer 증가
            lost를 -1로 변경
            reserve를 -1로 변경
            break
        }
    }
}
for(lost만큼) {
    for(reserve만큼) {
        if(앞이나 뒤 사람이 여벌을 가지고 있다면) {
            answer 증가
            reserve를 -1로 변경
            break
        }
    }
}
answer 리턴

코드 구현하기

/**
 * 42862) 체육복
 */
public class K001_42862 {
    // n(전체 학생의 수)
    // lost(체육복을 도난당한 학생들의 번호)
    // reserve(여벌의 체육복을 가져온 학생들의 번호)
    public int solution(int n, int[] lost, int[] reserve) {
        // answer(체육수업을 들을 수 있는 학생의 최댓값) = n - lost.length
        int answer = n - lost.length;
        // lost 정렬
        Arrays.sort(lost);
        // reserve 정렬
        Arrays.sort(reserve);
        // 여벌을 가져온 학생 중 도난 당한 학생이 있을 경우
        // +) Set을 통해서도 중복 제거 가능
        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] == reserve[j]) {
                    answer++;
                    lost[i] = -1;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        // 앞이나 뒤 사람이 여벌을 가지고 있다면
        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] - 1 == reserve[j] || lost[i] + 1 == reserve[j]) {
                    answer++;
                    reserve[j] = -1;
                    break;
                }
            }
        }
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K001_42862 solution = new K001_42862();

        int n = 5;
        int[] lost = { 2, 4 };
        int[] reserve = { 1, 3, 5 };

        int result = solution.solution(n, lost, reserve);

        System.out.println(result);
    }
}