[프로그래머스/JAVA] 체육복 (탐욕 알고리즘)

안녕하세요, 하루플 입니다.

프로그래머스의 체육복 문제인데 풀면서 조금 어려웠네요..😢

문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

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

 

제한사항

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

---

우선, 이 문제가 탐욕법(탐욕 알고리즘, Greedy Algorithms)😎 문제라고 되어있어서 무엇인지 알아보았습니다.

위키백과에서는 다음과 같이 나와있습니다.

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

 

쉽게 정리하면 다음과 같습니다.

- 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법. - 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘.

 

이제 전체 소스코드를 보겠습니다👀

 

[풀이]

        //여벌 옷을 가지고 있는 학생이 도난 당하면 빌려줄 수 없도록 만든다.
        for(int i=0; i<lost.length; i++){
            for(int j=0; j<reserve.length; j++){
                if(lost[i]==reserve[j]){ //도난 당한 학생 == 여벌옷 가져온 학생
                    lost[i] = reserve[j] = -1; //-1로 초기화
                    count++;
                    break;
                }
            }
        }

먼저, 여벌옷을 가지고 있는 학생이 도난 당했을 때는 빌려줄 수 없도록 합니다.

 

for문으로 lost.length (도난 당한 사람) 만큼 반복합니다.

2중 for문으로 reserve.length (여벌옷 가져온 사람) 만큼 반복합니다.

이후 도난 당한 학생과 여벌옷 가져온 학생끼리 서로 비교하여 같은 사람이 있는지 비교합니다.

만약 있으면 lost[i] 와 reserver[i] 를 모두 -1 로 초기화 합니다.

여기서 -1을 하는 이유는 다음 검사에 조건문에 포함이 되지 않도록 하기 위해서 입니다.

 

        //옷을 빌려주고 -1로 만들어 뒤의 학생에게 빌려주지 않게 한다.
        for(int k : lost){
            for(int j=0; j<reserve.length; j++){
                if(k == reserve[j]-1 || k == reserve[j]+1){
                    reserve[j] = -1;
                    count++;
                    break;
                }
            }
        }

이번엔 옷을 빌려주고 -1로 만들어 뒤의 학생에게는 빌려주지 않도록 하는 구문입니다.

 

lost를 int k에 값을 하나식 넣는 for문을 실행합니다.

2중 for문으로 reserve.length (여벌옷 가져온 사람) 만큼 반복합니다.

여벌옷 가져온 사람의 뒷사람과 앞사람(-1, +1)중 k 즉, lost 잃어버린 사람이 있다면

reserve[j] = -1을 하여 여벌옷 가져온 사람은 -1 을 하고, count를 증가시킵니다.

 

//결과값 : 전체 학생수 - 잃어버린 학생 수 + 빌린 학생 수
        answer = n - lost.length + count;
        return answer;

마지막으로 결과값인 전체 학생수 - 잃어버린 학생 수 + 빌린 학생 수를 return 해줍니다.

풀면서 조금 어려운 부분이 있어 다른 분들것도 코드를 참고하면서 풀어봤습니다!

설명 중 잘못된 부분이 있다면 댓글로 지적해주시면 감사드리겠습니다.