체육복

안녕하세요, 오늘은 오랜만에 코딩 테스트 연습 문제에 대한 글을 작성하려고 합니다.
오늘 같이 풀어볼 문제는 이전 문제들보다 조금 더 집중해서 지문을 확실히 해석하기 바랍니다.

📚 문제 설명

도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.

학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

 

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다.

체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육 수업을 들어야 합니다.

 

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가

담긴 배열 reserve가 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

코딩테스트 연습 - 체육복

📸 제한 사항

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

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

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

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

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

🗣 입출력 예시

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

첫 번째 예시를 보면 1번 학생이 2번 학생에게 체육복을 빌려주고 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 모두 체육수업을 들을 수 있습니다. 아래의 두 번째 예시를 본다면 3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다. 그러나 마지막 세 번째 예시에서는 1번 학생이 체육복을 아무한테도 빌려주지 못합니다.

 

📨 나의 해결책 (3시간 20분 소요)

# 멤버 변수

클래스 내부에 존재하는 member라는 ArrayList<Integer> 자료형의 멤버 변수는 프로그램 내에서 아주 중요한 역할을 담당합니다. 학생들 각각의 번호를 저장하며 체육복을 현재 가지고 있는 학생, 잃어버린 학생, 빌린 학생 등 학생들의 정보를 관리합니다.

ArrayList<Integer> member = new ArrayList<>();

# soltuion 메소드

solution 메소드는 전체 학생들의 수 n, 체육복을 잃어버린 학생들의 배열 lost, 여벌의 체육복을 가진 학생들의 배열 reserve를 인자로 전달 받으며 이를 활용해 각각의 메소드들을 호출하는 역할을 하며 최종적으로 체육 수업을 듣는 학생의 수를 반환합니다.

public int solution(int n, int[] lost, int[] reserve) {
    setMember(n);
    removeLostMember(lost);
    addReserve(n, lost, reserve);

    return member.size()
}

# setMember 메소드

setMember 메소드의 역할은 전달 받은 전체 학생들의 수 n 만큼 이전에 선언한 member 라는 리스트 멤버 변수에 학생들의 번호를 1부터 n까지 순차적으로 리스트에 데이터를 반복문을 활용하여 추가하고 있습니다. 이 과정을 통해 학생들의 번호가 저장됩니다.

public void setMember(int n) {
    for (int i = 1; i <= n; i++) {
        member.add(i);
    }
}

# removeLostMember 메소드

removeLostMember 메소드는 lost 배열 속 존재하는 체육복을 잃어버린 학생들의 번호를 member 리스트 배열에서 제거하는 역할을 합니다. 저희는 ArrayList 클래스의 removeAll 메소드를 사용하여 이 과정을 진행하며 매개변수로 제거할 번호를 전달합니다.

public void removeLostMember(int[] lost) {
   for (int lostValue : lost) {
       member.removeAll(Collections.singleton(lostValue));
   }
}

# addReserve 메소드

이 메소드에서는 먼저 여벌의 체육복을 가진 학생 또한 체육복을 도난당했는 학생인지 lost 배열과 비교합니다. 만약 여벌의 체육복을 가진 학생 역시 체육복을 도난당했다면 남은 체육복 한 개를 다른 친구에게 빌려줄 수 없으며 자신의 체육복으로 사용해야 합니다.

 

자신의 체육복으로 사용할 수 있도록 member 리스트 배열에 자신의 번호를 추가합니다. 그 후 reserve 배열 속에 존재하는 학생들이 각자 남은 체육복 1개를 다른 친구들에게 빌려줄 때 만약 그들의 차례가 온다면 continue를 통해서 다음 사람으로 바로 넘깁니다.

 

만약 위의 조건에 모두 해당하지 않고 자신의 체육복을 이미 가진 상태에서 여벌의 체육복을 가진 학생이라면 이 학생의 번호 앞 또는 뒤 학생에게 남은 여벌의 체육복 1개를 빌려줍니다. 이 과정 속에서 여벌의 체육복을 가진 학생은 앞 또는 뒤 학생들 중 단, 한 명에게만 체육복을 빌려줄 수 있으며 체육복을 빌려 받는 학생의 번호가 현재 member 리스트 배열에 미리 존재해서는 절대 안 됩니다.

public void addReserve(int n, int[] lost, int[] reserve) {
   for (int reserveValue : reserve) {
       for (int lostValue : lost) {
           if (lostValue == reserveValue) {
              member.add(reserveValue);
           }
        }
   }

   for (int reserveValue : reserve) {
       boolean overlapCheck = false;

       for (int lostValue : lost) {
           if (lostValue == reserveValue) {
              overlapCheck = true;
           }
       }
       if (overlapCheck) continue;

       int backValue = reserveValue - 1;
       int forwardValue = reserveValue + 1;

       if (backValue != 0 && !member.containsAll(Collections.singleton(backValue))) {
          member.add(backValue);
          continue;
       }

       if (forwardValue <= n && !member.containsAll(Collections.singleton(forwardValue))) {
          member.add(forwardValue);
       }
   }
}

[ 전체 소스코드 ]

class Solution {

    ArrayList<Integer> member = new ArrayList<>();

    public int solution(int n, int[] lost, int[] reserve) {
        setMember(n);
        removeLostMember(lost);
        addReserve(n, lost, reserve);

        return member.size();
    }

    public void setMember(int n) {
        for (int i = 1; i <= n; i++) {
            member.add(i);
        }
    }

    public void removeLostMember(int[] lost) {
        for (int lostValue : lost) {
            member.removeAll(Collections.singleton(lostValue));
        }
    }

    public void addReserve(int n, int[] lost, int[] reserve) {
        for (int reserveValue : reserve) {
            for (int lostValue : lost) {
                if (lostValue == reserveValue) {
                    member.add(reserveValue);
                }
            }
        }

        for (int reserveValue : reserve) {
            boolean overlapCheck = false;

            for (int lostValue : lost) {
                if (lostValue == reserveValue) {
                    overlapCheck = true;
                }
            }
            if (overlapCheck) continue;

            int backValue = reserveValue - 1;
            int forwardValue = reserveValue + 1;

            if (backValue != 0 && !member.containsAll(Collections.singleton(backValue))) {
                member.add(backValue);
                continue;
            }

            if (forwardValue <= n && !member.containsAll(Collections.singleton(forwardValue))) {
                member.add(forwardValue);
            }
        }
    }
}

🎨 모범 답안 (Greedy)

아래의 코드에서는 체육복을 도난당한 학생의 번호에 해당하는 배열의 인덱스 속의 값을 -1로 설정하고 반면에 여벌의 체육복을 가진 학생들의 경우 1로 초기 값을 설정했습니다. 그 후 아래의 조건은 제가 위에서 설명했던 것과 거의 유사한 형태로 이루어졌으나 약간의 색다른 관점을 통해서 조건문을 구성한 것을 볼 수 있었습니다. 그러나 결과적으로는 모범 답안 코드의 프로그램이 더 빨랐습니다.

public class Solution {

    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;

        for (int l : lost) {
            people[l - 1]--;
        }

        for (int r : reserve) {
            people[r - 1]++;
        }

        for (int i = 0; i < people.length; i++) {
            if (people[i] == -1) {
                if (i - 1 >= 0 && people[i -1] == 1) {
                    people[i]++;
                    people[i-1]--;
                } else if (i + 1 < people.length && people[i + 1] == 1) {
                    people[i]++;
                    people[i+1]--;
                } else {
                    answer--;
                }
            }
        }
        return answer;
    }
}

👍 글을 마치며

오늘은 체육복이라는 코딩 테스트 연습 문제를 풀어보았습니다. 처음에 제가 이 문제를 보았을 때 저는 약 30분 만에 문제에 대한 로직을 구성했으며 이를 코드로 구현했습니다. 하지만 제가 문제의 특정 제한사항을 똑바로 읽어보지 않아 오랫동안 작은 오류 때문에 삽집을 많이 하였습니다. 이를 통해 코딩 테스트 문제를 풀 때는 천천히 꼼꼼하게 문제를 이해하는 것이 중요하다고 생각했습니다.