프로그래머스 | 체육복, 그리디 알고리즘

문제

코딩테스트 연습 - 체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

n	lost	reserve	return
5	[2,4]	[1,3,5]	5
5	[2,4]	[3]	4
3	[3]	[1]	2

풀이

설명

• 해당 문제에서 놓치기 쉬운 점은 lost 배열과 reserve 배열에 중복된 데이터가 있으면 중복된 데이터는 여분의 체육복을 자신이 입는다는 것이다.
• 먼저 해당 문제를 풀기 위해 규칙을 설정했다.
  • 체육복을 도난 당한 사람(lost) → -1
  • 여분의 체육복을 가지고 있는 사람(reserve) → 1
  • 자신의 체육복만 가지고 있는 사람(두 배열에 속하지 않은 데이터) → 0

위의 규칙을 바탕으로 students 배열을 만들고, 해당 배열을 lost와 reserve 배열 만큼 반복한다.

• lost에 속하는 학생일 경우 → 해당 인덱스의 데이터 -1
• reserve에 속하는 학생일 경우 → 해당 인덱스의 데이터 +1

해당 과정을 마치고 나면 students 배열에 누가 없는지, 여분을 가지고 있는지 파악할 수 있으면서 lost와 reserve 배열에 중복되는 데이터는 0으로 만들어 해당 학생이 수업을 들을 수 있도록 만들 수 있다.

나의 경우 이전의 학생이 아닌 이후 학생부터 빌려줄 수 있는지 확인했는데, 11번 테스트 케이스에서 실패했었다.
해당 실패는 lost 배열에 {1,3,5}, reserve 배열에 {2,4,5}의 데이터가 존재한다고 가정했을 때, 나의 경우에서는 2번 학생이 3번 학생에게 체육복을 빌려주게되면서 수업을 들을 수 있는 학생수가 4명으로 최대 5명인 기대값과 다르다.

그렇기 때문에 이후의 학생부터가 아닌 이전의 학생부터 확인한다면 11번 테스트 케이스를 가뿐히! 통과할 수 있다. 다만, 나의 코드가 가독성도 좋지않고, 간결하지도 않다. 다른 분들의 코드를 보면서 더 어썸한 코드로 진화할 수 있도록 공부해야겠다!

코드

package 심성헌.알고리즘_6주차;

public class 체육복_프로그래머스_그리디 {
    public static void main(String[] args) {
        int n = 5;
        int[] lost = { 2, 4 };
        int[] reserve = { 3 };
        int result = solution(n, lost, reserve);

        System.out.println("\n" + result);
    }

    public static int solution(int n, int[] lost, int[] reserve) {
        // 학생수만큼 배열 구현
        int[] students = new int[n];
        // reserve 배열은 여분의 체육복을 가지고 있는 학생이다.
        // students 배열의 해당 학생의 체육복 + 1
        for (int idx : reserve) {
            students[idx - 1]++;
        }

        // lost 배열은 체육복을 도난 당한 학생이다.
        // students 배열의 해당 학생의 체육복 - 1
        for (int idx : lost) {
            students[idx - 1]--;
        }

        // 학생수 만큼 반복한다.
        for (int i = 0; i < students.length; i++) {
            int p = i + 1; // 현재 위치의 + 1
            int m = i - 1; // 현재 위치의 - 1
            // 현재 학생이 여분을 가지고 있다면
            if (students[i] == 1) {
                // 현재 학생 이전의 학생부터 확인
                if (m >= 0) {
                    if (students[m] == -1) {
                        students[i] = 0;
                        students[m] = 0;
                    }
                }
                // 현재 학생 다음의 학생 확인
                if (p < students.length) {
                    if (students[p] == -1 && students[i] != 0) {
                        students[i] = 0;
                        students[p] = 0;
                    }
                }
            }
        }

        // 체육복을 입고 수업에 참여할 수 있는 학생의 수
        int cnt = 0;
        for (int a : students) {
            System.out.print(a + " ");
            if (a > -1)
                cnt++;
        }
        return cnt;
    }
}