[프로그래머스(programmers)] level 1 체육복 탐욕법(greedy) 문제 자바 풀이

이번에는 프로그래머스 level 1 문제도 풀어보았어요

level2 문제를 풀어보고 있었는데 level 1 부터 차례대로 정복해 나가려구요!!

아무튼 level 1 체육복 문제는 탐욕법, greedy 문제로 분류되어 있어요

 

이 문제는 양 옆의 사람이 여벌의 옷을 들고 있는지 확인하여 빌림으로써 간단히 풀 수 있어요!!

그런데 처음 사람은 왼쪽 사람이 없고 마지막 사람은 오른쪽 사람이 없으므로

맨 왼쪽과 맨 오른쪽에 칸을 추가해서 쉽게 비교할 수 있도록 합니다

옷이 없는 학생은 -1, 여벌 옷이 있는 학생은 1, 자기 입을 옷 하나만 있는 학생은 0입니다.

그렇게 왼쪽이나 오른쪽에서 1인 사람이 있다면 옷을 빌리고 값을 업데이트 해줍니다

 

프로그래머스 체육복 자바 코드는 다음과 같습니다!

자세한 해설이나 코드는 github에서 볼 수 있습니다

https://github.com/wlgh325/Programmers_algorithm/tree/master/Level1/%EC%B2%B4%EC%9C%A1%EB%B3%B5

wlgh325/Programmers_algorithm

 

import java.util.ArrayList;
import java.util.Collections;

class Solution{
    public int solution(int n, int[] lost, int[] reserve) {
        int[] clothes = new int[n+2];
        int answer = n;
        clothes[0] = -10;
        clothes[n+1] = -10;


        for(int i=0; i<lost.length; i++){
            clothes[lost[i]] -= 1;
        }

        for(int i=0; i<reserve.length; i++){
            clothes[reserve[i]] += 1;
        }

        for(int i=0; i<=n; i++){
            // 체육복이 없다면
            if(clothes[i] == -1){
                // 왼쪽 학생이 여벌 옷이 있다면 빌림
                if(clothes[i-1] == 1){
                    clothes[i-1] -= 1;
                    clothes[i] += 1;
                }
                // 오른쪽 학생이 여별 옷이 있다면 빌림
                else if(clothes[i+1] == 1){
                    clothes[i+1] -= 1;
                    clothes[i] += 1;
                }
                // 빌릴 수 없다면
                else{
                    answer --;
                }
            }
        }

        return answer;
    }
}