Java 프로그래머스 체육복 자바

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

프로그래머스

---

[문제 설명]

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다.

다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.

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

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다.

체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

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

[제한사항]

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

[입출력 예]

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

[입출력 예 설명]

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면,

학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

[문제 풀기 전 생각/정리]

탐욕법에 속해있는 문제라서 탐욕법에 대해서 찾아봤다.

탐욕법(Greedy Algorithms)이란?
최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

쉽게 말해서, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다.

가능한 경우의 수 내에서 최적의 해답을 찾는 것이다.(물론 내 풀이가 최적이 아닐 수 있다.)

• 가장 까다로운 다섯 번째 제한사항을 먼저 처리한다.
• n = 5, lost = [1, 2, 3],  reserve = [2,3,4]라고 생각해 보면, 5번을 나중에 처리한다고 가정했을 때, 1 → 2번을 빌리고 2 → 3번  3 → 4번 을 빌린다. 이렇게 빌리면 5명 모두가 가능하다.
• 5번을 최우선 처리하면, 2,3은 배열에서 제외(변형)돼서, lost = [1, -1, -1], reserve = [-1, -1, 4]가 된다. 1번 학생은 빌릴 학생이 없기 때문에 4명만이 가능!!

[나의 풀이]

import java.util.Arrays;

public class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;

        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        //여벌 체육복 있는애가 도둑맞은 경우
        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;
                }
            }
        }
        
        //자기번호 +1, -1인 번호에게만 대여가능
        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;
    }
}

• 첫 번째 if문에서 lost[i]와 reserve[j]가 같은 경우, 다음 조건에서 제외 대상이므로 -1로 치환
• 두 번째 반복문은 뒤의 학생에게는 빌려주지 않도록 하는 구문으로, 2중 for문 중 reserve.length (여벌옷 가져온 사람) 만큼 반복
• 여벌옷 가져온 사람의 뒷사람과 앞사람(-1, +1) 중, 잃어버린 사람이 있다면
• reserve[j] = -1을 하여 여벌옷 가져온 사람은 -1을 하고, answer 증가

[정리]

개인 피셜 난이도 : ★★☆☆☆

제한사항과 테스트케이스가 업데이트되면서 오류가 난 코드가 일부 있어서,

다른 사람들의 풀이는 생략했다.

 

역시나 알고리즘은 100번 읽고 공부하고 하는 것보다,

직접 코딩하는 게 훨씬 이해도 잘 되는 것 같다.

그리고 간단한 주석이라도 남겨 놓지 않으면 까먹을 수 있으니,

이렇게 블로그에 리뷰하고 남기는 게 좋은 것 같다.

 

언제나 새로운 정보 공유와 잘못된 정보

비판/지적/태클은 환영입니다!

끝.