[Programmers] 체육복

체육복

문제 분석

자세한 설명은 링크 참고.

n = 학생 수

lost = 체육복 없는 학생들

reserve = 여분의 체육복이 있는 학생들

return = 결과값

1번 예시

n = 학생 수는 5명이다.

lost = 2, 4번 학생이 체육복이 없다.

reserve = 1, 3, 5번 학생이 여분의 체육복이 있다.

return = 5명이 모두 체육복을 가지고 수업에 참여가 가능하다.

여분의 체육복은 좌, 우만 빌려줄 수 있다.

여분의 체육복이 있으면서 잃어버릴 수도 있다.

풀이 과정

🎯 그리디

주어진 상황에서 가장 최선의 선택만을 고르는 알고리즘.

이 문제를 보자면, 여분의 체육복을

좌, 우 학생에게 빌려줄 수 있기 때문에

왼쪽에 빌려줄지, 오른쪽에 빌려줄지

가장 최선의 상황만을 선택해야 한다.

아래의 상황을 보자.

학생1

학생2

학생3

학생4

학생5

학생6

학생7

학생8

학생9

빨간색 학생은 체육복을 잃어버렸다.

초록색 학생은 여분의 체육복이 있다.

흰색 학생은 본인 것만 있다.

학생2가 오른쪽 학생3 한테 빌려주게 된다면

학생1

학생2

학생3

학생4

학생5

학생6

학생7

학생8

학생9

학생2 -> 학생3

학생4 -> 학생5

학생6 -> 학생7

위와 같이 빌려주게 되면서 문제가 해결될 것이고,

학생2가 왼쪽 학생1 한테 빌려주게 된다면

학생1

학생2

학생3

학생4

학생5

학생6

학생7

학생8

학생9

학생2 -> 학생1

학생4 -> 학생3

학생6 -> 학생5

학생8 -> 학생7

위와 같이 빌려주게 돼서 문제가 해결될 것이다.

최선의 선택은 학생2가 오른쪽 학생이 아닌, 왼쪽 학생에 빌려주면서 문제를 해결하는 것이다.

🎯 체육복 누가 있고 누가 없나?

lost = 체육복을 잃어버린 학생들

reserve = 여분의 체육복을 가지고 있는 학생들

문제는 lost 와 reserve 에 둘 다 있을 수 있다.

여벌 체육복을 가져오고, 잃어버렸다면 본인 것만 있는 것이다.


        int[] student = new int[n + 1]; // 학생 수로 배열을 선언한다.

        for (int i = 0; i <= n; i++) {
            student[i] = 1;
        } // 우선 모든 학생은 1벌의 체육복을 가지고 있고

        for (int i = 0; i < reserve.length; i++) {
            student[reserve[i]]++;
        } // 여분을 가져온 학생을 추가해준다.

        for (int i = 0; i < lost.length; i++) {
            student[lost[i]]--;
        } // 잃어버린 학생을 추가해준다.

학생 수로 배열을 선언해주고,

첫 번째 for : 모든 학생은 1벌의 체육복이 있다.

두 번째 for : 여벌의 체육복을 가져온 학생 갱신

세 번째 for : 체육복을 잃버러니 학생 갱신

🎯 여분이 있는 학생, 잃어버린 학생

1벌이 있으면 빌려주지 않는다.

2벌이 있으면 빌려준다.

좌, 우 중 한 곳에 빌려줄 수 있다.

왼쪽 학생이 체육복이 없다면,


if (i - 1 >= 1 && student[i - 1] == 0) {
    student[i - 1]++;
    student[i]--;
    continue;
}

오른쪽 학생이 체육복이 없다면,


if (i + 1 < student.length && student[i + 1] == 0) {
    student[i + 1]++;
    student[i]--;
    continue;
}

핵심 로직 전체 코드


        for (int i = 1; i < student.length; i++) {
            if (student[i] == 2) { // 체육복이 2벌이라면,

                if (i - 1 >= 1 && student[i - 1] == 0) {
                    student[i - 1]++;
                    student[i]--;
                    continue;
                }

                if (i + 1 < student.length && student[i + 1] == 0) {
                    student[i + 1]++;
                    student[i]--;
                    continue;
                }
            }
        }

나의 생각

위의 문제는 왼쪽 학생을 먼저 빌려주는 로직만이 통과가 된다.

왼쪽 학생 먼저 vs 오른쪽 학생 먼저 중 큰 값이 정답이 아니다.

(물론 정답이다, 다만 추가 로직이 불필요하다.)

오른쪽 학생부터 빌려주게 되면 왜 항상 값이 작을까?

배열을 왼쪽에서부터 탐색하기 때문에

왼쪽을 빌려줄 수 없는 경우의 수로 시작하게 된다.

오른쪽부터 빌려주게 되면 왼쪽 학생이 여분의 체육복을 못 받는 경우가 있기 때문에 왼쪽 부터 빌려주는 경우의 수보다 적을 것이다.

코드


import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;

        int[] student = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            student[i] = 1;
        }

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

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

        // System.out.println(Arrays.toString(student) + " < < < ");

        for (int i = 1; i < student.length; i++) {
            if (student[i] == 2) {

                if (i - 1 >= 1 && student[i - 1] == 0) {
                    student[i - 1]++;
                    student[i]--;
                    continue;
                }

                if (i + 1 < student.length && student[i + 1] == 0) {
                    student[i + 1]++;
                    student[i]--;
                    continue;
                }
            }
        }

        // System.out.println(Arrays.toString(student) + " < < < ");

        for (int i = 1; i <= n; i++) {
            if (student[i] >= 1) answer++;
        }

        return answer;
    }
}