programmers) 체육복 | 두번째풀이

👉프로그래머스 체육복 문제

---

문제 설명

전체 학생 수 n명이 있고, 일부 학생은 체육복을 도난당했다.

또 일부 학생은 여벌 체육복을 가지고 있다.

체육복을 도난당한 학생은 바로 앞번호나 바로 뒷번호 학생에게만 체육복을 빌릴 수 있다.

즉, i번 학생은 아래 학생에게만 빌릴 수 있다.

i - 1번 학생
i + 1번 학생

체육복을 빌려줄 수 있는 학생은 여벌 체육복을 가진 학생뿐이고, 여벌 체육복은 한 벌만 빌려줄 수 있다.

이때 체육 수업을 들을 수 있는 학생의 최댓값을 구해야 한다.

---

문제 유형 분류

이 문제는 그리디 문제이다.

체육복을 도난당한 학생을 앞번호부터 확인하면서, 빌릴 수 있는 학생이 있으면 바로 빌리는 방식으로 접근할 수 있다.

이 문제에서 중요한 점은 앞번호부터 차례대로 처리해야 한다는 것이다.

예를 들어 도난당한 학생이 i라면 다음 순서로 확인한다.

1. i - 1번 학생이 여벌 체육복을 가지고 있는지 확인한다.
2. 없다면 i + 1번 학생이 여벌 체육복을 가지고 있는지 확인한다.
3. 빌렸다면 해당 여벌 체육복은 다시 사용할 수 없게 처리한다.

---

입력 범위 확인

학생 번호는 1번부터 n번까지 있다.

lost 배열에는 체육복을 도난당한 학생 번호가 들어 있고,
reserve 배열에는 여벌 체육복이 있는 학생 번호가 들어 있다.

이 문제에서 주의해야 할 점은 lost와 reserve에 같은 학생이 동시에 들어 있을 수 있다는 것이다.

예를 들어 아래와 같은 경우이다.

lost = [2, 4]
reserve = [2, 3]

2번 학생은 체육복을 도난당했지만, 여벌 체육복도 가지고 있다.

이 경우 2번 학생은 자기 체육복을 입을 수는 있지만, 다른 학생에게 빌려줄 수는 없다.

따라서 이런 학생은 먼저 lost와 reserve 양쪽에서 제외해줘야 한다.

---

처음 접근

처음에는 체육복이 없는 학생 목록을 따로 만들고, 여벌이 있는 학생을 따로 표시하려고 했다.

즉, 이런 식으로 생각했다.

체육복 없는 학생 목록 만들기
여벌 체육복 있는 학생 표시하기
없는 학생이 앞뒤 학생에게 빌릴 수 있는지 확인하기

방향 자체는 나쁘지 않았다.

하지만 처음 코드에서는 이중 반복문 안에서 체육복 없는 학생을 리스트에 추가하다 보니, 같은 학생이 여러 번 들어가는 문제가 생겼다.

또 리스트를 순회하면서 remove()를 사용하려고 하면서 인덱스와 학생 번호가 헷갈리는 문제도 있었다.

이후에는 lost와 reserve 배열을 정렬한 뒤, 이미 처리한 학생을 -1로 표시하는 방식으로 수정했다.

---

핵심 예외 처리: 도난당했지만 여벌도 있는 학생

가장 먼저 처리해야 하는 것은 lost와 reserve에 동시에 있는 학생이다.

이 학생은 자기 체육복 문제는 해결할 수 있지만, 다른 학생에게 빌려줄 수는 없다.

그래서 먼저 두 배열에서 해당 학생을 -1로 표시해 제외했다.

for (int i = 0; i < lost.length; i++) { 
    for (int j = 0; j < reserve.length; j++) {
        if (lost[i] == reserve[j]) {
            lost[i] = -1;
            reserve[j] = -1;
            answer++;                    
            break;
        } 
    } 
}

여기서 answer는 체육 수업을 들을 수 있는 학생 수이다.

처음에는 체육복을 도난당한 학생 수만큼 제외해서 시작했다.

int answer = n - lost.length;

그런데 도난당했지만 여벌도 있는 학생은 결국 수업을 들을 수 있으므로 answer++를 해주었다.

---

학생 번호와 배열 인덱스가 헷갈렸던 부분

이번 문제에서 가장 헷갈렸던 부분은 배열의 원소가 학생 번호라는 점이었다.

예를 들어 아래 배열이 있다고 하자.

lost = [2, 4]

이때 i는 배열 인덱스이고, lost[i]는 학생 번호이다.

i = 0, lost[i] = 2
i = 1, lost[i] = 4

처음에는 학생 번호와 배열 인덱스를 헷갈려서 아래처럼 접근하려고 했다.

lost[less] = -1;

하지만 less는 학생 번호이다.

만약 less = 4라면 lost[4]에 접근하게 되는데, lost 배열의 길이가 2라면 인덱스 범위를 벗어난다.

그래서 배열 값을 수정할 때는 반드시 인덱스 i, j를 사용해야 한다.

lost[i] = -1;
reserve[j] = -1;

이번 문제에서 꼭 기억해야 할 점은 아래와 같다.

i, j는 배열 인덱스
lost[i], reserve[j]는 학생 번호

---

체육복 빌려주기

겹치는 학생을 먼저 처리한 뒤, 남은 도난 학생을 확인한다.

아직 체육복이 없는 학생이라면, 여벌 체육복을 가진 학생 중 번호 차이가 1인 학생을 찾는다.

for (int i = 0; i < lost.length; i++) {
    if (lost[i] == -1) continue;

    for (int j = 0; j < reserve.length; j++) {
        if (reserve[j] == -1) continue;

        if (Math.abs(lost[i] - reserve[j]) == 1) {
            reserve[j] = -1;
            answer++;
            break;
        }
    }
}

Math.abs(lost[i] - reserve[j]) == 1이라는 조건은 두 학생 번호가 바로 앞뒤 관계인지 확인하는 조건이다.

예를 들어 4번 학생은 3번 또는 5번 학생에게만 빌릴 수 있다.

체육복을 빌려준 학생은 다시 빌려줄 수 없으므로 reserve[j] = -1로 표시했다.

---

최종 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(reserve);
        Arrays.sort(lost);

        int answer = n - lost.length;

        for (int i = 0; i < lost.length; i++) { 
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] == reserve[j]) {
                    lost[i] = -1;
                    reserve[j] = -1;
                    answer++;                    
                    break;
                } 
            } 
        }

        for (int i = 0; i < lost.length; i++) {
            if (lost[i] == -1) continue;

            for (int j = 0; j < reserve.length; j++) {
                if (reserve[j] == -1) continue;

                if (Math.abs(lost[i] - reserve[j]) == 1) {
                    reserve[j] = -1;
                    answer++;
                    break;
                }
            }
        }
                
        return answer;
    }
}

---

코드 흐름 정리

전체 풀이 흐름은 다음과 같다.

1. lost와 reserve를 오름차순 정렬한다.
2. 전체 학생 수에서 도난당한 학생 수를 뺀 값을 answer로 시작한다.
3. lost와 reserve에 동시에 있는 학생을 먼저 처리한다.
   - 해당 학생은 수업을 들을 수 있으므로 answer++
   - lost와 reserve에서는 -1로 표시해 제외한다.
4. 남은 lost 학생들을 확인한다.
5. reserve 학생 중 번호 차이가 1인 학생을 찾는다.
6. 빌릴 수 있으면 answer++ 하고, 빌려준 reserve 학생은 -1로 표시한다.
7. 최종 answer를 반환한다.

---

시간 복잡도

이 풀이에서는 이중 반복문을 두 번 사용했다.

첫 번째 이중 반복문은 lost와 reserve에 동시에 있는 학생을 찾기 위한 반복문이다.

for (int i = 0; i < lost.length; i++) {
    for (int j = 0; j < reserve.length; j++) {
        ...
    }
}

두 번째 이중 반복문은 체육복을 빌릴 수 있는 학생을 찾기 위한 반복문이다.

for (int i = 0; i < lost.length; i++) {
    for (int j = 0; j < reserve.length; j++) {
        ...
    }
}

따라서 시간복잡도는 다음과 같다.

O(L * R)

여기서 L은 lost.length, R은 reserve.length이다.

최악의 경우 두 배열의 길이가 모두 N에 가깝다면 다음과 같이 볼 수 있다.

시간복잡도: O(N^2)

정렬까지 포함하면 더 정확히는 아래와 같다.

O(L log L + R log R + L * R)

하지만 이중 반복문이 핵심이므로 최악의 경우 O(N^2)으로 정리했다.

---

공간 복잡도

이번 풀이에서는 별도의 리스트나 상태 배열을 사용하지 않았다.

기존 lost, reserve 배열 값을 직접 -1로 바꿔서 처리 여부를 표시했다.

따라서 추가 공간은 거의 사용하지 않는다.

공간복잡도: O(1)

단, 정렬 과정에서 내부적으로 추가 공간이 사용될 수 있지만, 직접 만든 추가 자료구조 기준으로는 O(1)이라고 볼 수 있다.

---

상태 배열 방식과 비교

이 문제는 상태 배열 방식으로도 풀 수 있다.

상태 배열 방식은 학생마다 체육복을 몇 벌 가지고 있는지 저장하는 방식이다.

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

처음에는 모든 학생이 체육복을 1벌 가지고 있다고 보고, 도난당한 학생은 1 감소, 여벌이 있는 학생은 1 증가시킨다.

clothes[i] == 0 → 체육복 없음
clothes[i] == 1 → 체육복 있음
clothes[i] == 2 → 여벌 있음

이 방식은 lost와 reserve에 동시에 있는 학생도 자연스럽게 처리된다.

예를 들어 2번 학생이 도난도 당하고 여벌도 있으면 다음과 같이 된다.

처음: 1
도난 처리: 0
여벌 처리: 1

결국 자기 체육복은 입을 수 있지만, 다른 사람에게 빌려줄 여벌은 없는 상태가 된다.

상태 배열 방식은 시간복잡도는 O(N), 공간복잡도는 O(N)이다.

반면 내가 푼 방식은 기존 배열을 직접 수정해서 공간은 적게 쓰지만, 이중 반복문을 사용하기 때문에 시간복잡도는 O(N^2)이다.

내 풀이: 시간복잡도 O(N^2), 공간복잡도 O(1)
상태 배열 풀이: 시간복잡도 O(N), 공간복잡도 O(N)

---

이번 풀이에서 배운 점

이번 문제는 그리디 문제였지만, 구현 과정에서 배열 인덱스와 배열 원소의 차이를 다시 정리할 수 있었다.

특히 아래 개념이 중요했다.

i, j는 배열 인덱스
lost[i], reserve[j]는 학생 번호

학생 번호가 숫자로 되어 있다 보니 인덱스처럼 착각하기 쉬웠다.

또 lost와 reserve에 동시에 있는 학생을 먼저 처리해야 한다는 점도 중요했다.

이 처리를 하지 않으면 도난당했지만 여벌도 있는 학생이 다른 학생에게 체육복을 빌려주는 것으로 잘못 계산될 수 있다.

---

셀프 체크

왜 처음에 바로 풀지 못했는가?

처음에는 체육복 없는 학생 목록과 여벌 체육복이 있는 학생 목록을 따로 관리하려고 했다.

방향은 맞았지만, 리스트에 같은 학생이 중복으로 들어가거나 리스트를 순회하면서 삭제하는 문제가 생겼다.

시간이 부족했는가?

시간보다는 구현 과정에서 인덱스와 학생 번호를 헷갈린 것이 더 큰 원인이었다.

문제 해석을 잘못했는가?

문제의 큰 방향은 이해했지만, lost와 reserve에 동시에 있는 학생을 먼저 처리해야 한다는 예외 조건을 놓칠 수 있었다.

자료구조 선택을 잘못했는가?

처음에는 리스트를 사용하려고 했지만, 오히려 구현이 복잡해졌다.

최종적으로는 기존 배열을 -1로 표시하면서 처리했다.

상태 배열을 사용하면 더 단순하게 풀 수도 있다.

엣지 케이스를 놓쳤는가?

도난당했지만 여벌도 있는 학생이 가장 중요한 엣지 케이스였다.

예를 들어 아래와 같은 경우이다.

lost = [2, 4]
reserve = [2, 3]

2번 학생은 자기 체육복 문제만 해결할 수 있고, 다른 학생에게 빌려줄 수 없다.

구현 실수가 있었는가?

학생 번호와 배열 인덱스를 헷갈렸다.

처음에는 lost[less] = -1처럼 작성하려고 했는데, less는 학생 번호이므로 배열 인덱스로 사용하면 안 된다.

올바른 방식은 현재 반복문의 인덱스를 사용해 아래처럼 수정하는 것이다.

lost[i] = -1;
reserve[j] = -1;

시간 복잡도 판단을 잘못했는가?

최종 풀이 기준으로는 이중 반복문을 사용하므로 최악의 경우 O(N^2)이다.

상태 배열을 사용하면 O(N)으로 줄일 수 있다.

이번 문제에서는 입력 범위가 크지 않기 때문에 내가 작성한 O(N^2) 풀이도 충분히 통과 가능하다.