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

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

코드:https://github.com/irerin07/AlgorithmStudyBaek/blob/master/src/programmers_lvl_1/programmers42862.java

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class programmers42862 {
    public static void main(String[] args) {
        int n = 7;
        int[] lost = {2,3,4};
        int[] reserve = {1,2,3,6};
        System.out.println(solution(n, lost, reserve));

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

        HashSet<Integer> res = new HashSet<Integer>();

        for(int k : reserve) {
            res.add(k);
        }

        //체육복을 2벌 가지고 있지만 하나를 도둑맞은 경우
        for(int i = 0; i < lost.length; i++){
            if(res.contains(lost[i])){
                answer++; //참가 가능한 학생의 수를 늘려주고
                res.remove(lost[i]); //여분 체육복을 가진 학생의 리스트에서 내리고
                lost[i] = -1; //lost[i]를 -1로 변경하여 제외시킨다.
            }
        }

        //여분이 없고 체육복을 도둑맞아 빌려야 하는 경우
        for(int i = 0; i < lost.length; i++){
            if(res.contains(lost[i]-1)){
                answer++;
                res.remove(lost[i]-1);
            }else if(res.contains(lost[i] + 1)){
                answer++;
                res.remove(lost[i]+1);
            }
        }

        return answer;
    }
}

 

Greedy Algorithm 문제

 

각 상황마다 가장 최선의 답을 골라서 선택하는 알고리즘이다.

 

체육복을 빌려야 하는 경우에 내 앞번호와 뒷번호의 사람이 여분을 가지고 있는지 확인하여

가지고 있을 경우 빌리고 없으면 넘어가는 식의 단순한 문제이다.

 

만약 내가 체육복을 두벌 가지고 있고 한벌을 도둑맞았을 경우엔 내가 여분의 체육복을 사용해야 하므로 

내 앞번 혹은 뒷번호의 사람이 체육복을 잃어버렸어도 빌려줄 수 없다는 것을 생각해서 풀어야 했다.

 

풀이는 금방 생각이 났는데 구현이 오래 걸렸다.