[programmers] 체육복 - Java

체육복

문제 설명

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.

• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.

• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.

• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.

• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

solution.java

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // uniforms 배열을 1로 초기화
        int[] uniforms = new int[n + 1];
        Arrays.fill(uniforms, 1);

        // lost, reserve 배열로 uniforms 배열 초기화
        for (int l : lost) {
            uniforms[l]--;
        }
        for (int r : reserve) {
            uniforms[r]++;
        }

        // 가능한 경우 교복 빌려주기
        for (int i = 1; i <= n; i++) {
            if (uniforms[i] == 0) { // 만약 유니폼이 없는 학생이라면
                if (i > 1 && uniforms[i - 1] == 2) { // 이전 학생 확인
                    uniforms[i]++;
                    uniforms[i - 1]--;
                } else if (i < n && uniforms[i + 1] == 2) { // 다음 학생 확인
                    uniforms[i]++;
                    uniforms[i + 1]--;
                }
            }
        }

        // 유니폼을 하나 이상 소지한 학생 카운트
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (uniforms[i] > 0) {
                count++;
            }
        }

        return count;
    }
}

핵심 키워드

• 배열을 1로 초기화한 후, 잃어버린 순서와 예비를 가져온 사람들을 순회하며 초기화 한다.

• 배열을 처음부터 순회하며 값이 0인 인덱스의 앞 뒤로 값을 조회하고, 만약 2라면 해당 인덱스의 값을 -1, +1하며 조정한다.

결론!

• 탐욕법이란 해당 순간에 최적인 답을 선택하여 결과를 도출하는 알고리즘이다.

• 해당 문제의 경우 배열을 통해 이전 순서와 다음 순서의 결괏값을 접근하고, 해당 순서의 결괏를 도출해낼 수 있었다.