체육복_복습3

2026.10.12

문제 풀이

나의 코드

소요 시간: 9분
시간 복잡도: $O(n)$

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] students = new int[n + 2];
        for (int stolen : lost) {
            students[stolen]--;
        }
        for (int spare : reserve) {
            students[spare]++;
        }
        for (int i = 1; i < students.length; i++) {
            if (students[i] == -1) {
                if (students[i - 1] == 1) {
                    students[i - 1]--;
                    students[i]++;
                } else if (students[i + 1] == 1) {
                    students[i + 1]--;
                    students[i]++;
                }
            }
        }
        for (int i = 1; i < students.length; i++) {
            if (students[i] == -1) {
                n--;
            }
        }
        return n;
    }
}

---

AI 코드

시간 복잡도: $O(n)$

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] students = new int[n + 2];          // 1~n 사용, 양쪽에 여유 1칸
        for (int l : lost) students[l]--;
        for (int r : reserve) students[r]++;

        int answer = n;
        for (int i = 1; i <= n; i++) {
            if (students[i] != -1) continue;
            if (students[i - 1] == 1) { students[i - 1]--; students[i]++; }
            else if (students[i + 1] == 1) { students[i + 1]--; students[i]++; }
            else answer--;                        // 앞뒤 모두 없으면 수업 불가
        }
        return answer;
    }
}

문제 풀이 후기

난이도가 낮은 문제인데다가 3번째 복습이라 푸는 방법을 외워 버렸다.
그래서 HashSet 으로만 해결하다가 이번엔 배열을 이용해서 풀어봤다.