[PGS] 프로그래머스 - 체육복 (JAVA)

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

프로그래머스

import java.util.*;
import java.io.*;

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]){
                    lost[i] = -1;
                    reserve[j] = -1;
                    answer++;
                    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]){
                    reserve[j] = -1;
                    answer++;
                    break;
                }
            }
        }

        
        return answer;
    }
}

1. 여벌의 체육복을 가지고 있지만 도난을 당한 경우, 내가 내꺼 입으면 되기때문에 도난당한 명단, 빌려줄 수 있는 명단에서 제외한 뒤 answer을 증가시킨다.

2. 도난 당했지만 앞, 뒤에 빌려줄 수 있는 사람이 있는 경우 빌리고 answer을 증가시킨다.

* 정렬이 되지 않은 채 input이 들어오는 경우가 있어 먼저 lost와 reserve배열을 정렬시켜준다.

 

그리디 알고리즘

: 매 순간 최고의 선택을 하자 !

-> 무조건 00한대로 선택하는 경우가 많아 정렬이 함께 이용되는 경우가 많다.