[프로그래머스] 체육복 - 자바

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

프로그래머스

문제 풀이

그리디 알고리즘으로 최적의 상황을 선택해서 풀이한다. 도저히 몇십분 고민하면서 삽질하다가 

대부분 코드가 비슷했지만 https://haruple.tistory.com/190 이분 풀이로 해결했다. 다른 블로그를 보더라도 그리디 알고리즘을 적용했을 때 왜 그 알고리즘이 최적의 상황을 선택한건지 이해해야 한다. 위 링크의 알고리즘도 왜 이게 최적일까 한참 고민했고 이해한 방법을 설명하겠다

이 코드는 도난당한 학생에게 대여를 해주는 코드이다.

위 코드를 봤을 때 왜 이 코드가 모든 경우에 대해 최적의 상황을 고려할 수 있는가?에 대해 생각했어야 한다.

여기서 중요한 점이 왜 저 코드가 최적의 상황일까? 맨 처음 들었던 생각은 reverse(대여가능학생)가 O, lost(도난당한학생) X 로 두었을 때 OXOX의 학생들이 있다고 치자. 3번째인 O의 학생이 2번째 X에게 대여를 해주면 4번째 X학생은 대여를 받지 못한다.

당연히 인용한 코드는 정답 코드이니 이 알고리즘은 최적의 상황을 고려하고 OXOX 상황에서도 4명의 학생이 모두 대여를 받을 수 있도록 보장한다.

 

해당 코드는 k:lost에서 도난당한 학생에 대해 무조건 왼쪽부터 대여를 받는다. 그리고 대여를 해주는 학생도 무조건 왼쪽부터 대여해주기 때문에 순차적으로 빠지는 사람없이 대여를 해줄 수 있다. 듣고나면 당연한 말을 어렵다는 듯이 써놨구나 싶지만 막상 풀거나 다른 분들의 코드를 보면 이게 왜 맞나 싶을 것이다..

 

추가로 해당 링크는 정렬이 안되어 있지만 문제 개편되면서 정렬을 해야 성공한다.

코드

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0; //체육수업 들을 수 있는 학생의 최대값
        int count = 0; //빌린 학생 수
        
        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]){ //도난 당한 학생 == 여벌옷 가져온 학생
                    lost[i] = reserve[j] = -1; //-1로 초기화
                    count++;
                    break;
                }
            }
        }
        
        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;
                }
            }
        }
        
        //결과값 : 전체 학생수 - 잃어버린 학생 수 + 빌린 학생 수
        answer = n - lost.length + count;
        return answer;
    }
}

느낀점

그리디는 공식이 있는 알고리즘이 아니라 정말 머리로 푸는 센스 개념인 것 같다.