[프로그래머스/Java] 체육복(Greedy 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 greedy 알고리즘 문제 중 하나인 '체육복'을 자바로 풀어보았다. 

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

프로그래머스

 

 

Greedy 알고리즘에 대한 설명은 아래 블로그 글을 참고했다. Greedy를 너무 오랜만에 접하는 거라서 어떤 방법으로 문제에 접근해야 하는지 파악하기 위해서 읽어보았다. 

https://memodayoungee.tistory.com/103

[알고리즘] Greedy Algorithm(탐욕 알고리즘)

 

 

 풀이는 아래와 같다. 딱히 어려운 부분은 없다. 학생들이 각각 가진 체육복의 개수를 세어둘 배열을 만든다는 것만 생각해 내면 어렵지 않게 풀 수 있다. 

 Arrays.fill() 을 처음 사용해 보았다. c언어에서 loop를 사용하던 것에 익숙해서 매번 그렇게 했었는데, 유용하게 사용할 것 같다. 

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] nums = new int[n+1];
        Arrays.fill(nums, 1);
        
        for (int l : lost) nums[l]--;
        for (int r : reserve) nums[r]++;
        
        for (int i = 1; i <= n; i++) {
            if (nums[i] < 2) continue;
            if ((i-1) > 0 && nums[i-1] == 0) nums[i-1]++;
            else if ((i+1) <= n && nums[i+1] == 0) nums[i+1]++;
            nums[i]--;
        }
        
        for (int i = 1; i <= n; i++) {
            if (nums[i] > 0) answer++;
        }
        return answer;
    }
}