체육복_복습2

2026.10.07

문제 풀이

1차 실행 오류

90.0/100.0
실패

실패 원인 분석

체육복을 잃어버린 학생에 대해
오름차순으로 자신의 앞 번호 학생을 먼저 조회해야 한다.
따라서 lost 배열의 정렬이 필요하다.

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> spare = new HashSet<>(); // 여벌 체육복을 가지고 있는 학생
        for (int r : reserve) {
            spare.add(r);
        }
        Set<Integer> stolen = new HashSet<>(); // 체육복을 도둑맞은 학생
        for (int l : lost) {
            stolen.add(l);
            if (spare.contains(l)) {
                stolen.remove(l);
                spare.remove(l);
            } else if (spare.contains(l - 1)) {
                stolen.remove(l);
                spare.remove(l - 1);
            } else if (spare.contains(l + 1)) {
                stolen.remove(l);
                spare.remove(l + 1);
            }
        }
        return n - stolen.size();
    }
}

2차 실행 오류

93.3/100.0
실패

실패 원인 분석

체육복을 가지고 있는 학생이 체육복을 도난당했을 때,
해당 학생은 체육복을 빌려줄 수 없다.
그러나 앞 번호에서 미리 빌려가는 경우가 생길 수 있다.

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> spare = new HashSet<>(); // 여벌 체육복을 가지고 있는 학생
        for (int r : reserve) {
            spare.add(r);
        }
        
        Arrays.sort(lost);
        Set<Integer> stolen = new HashSet<>(); // 체육복을 도둑맞은 학생
        for (int l : lost) {
            stolen.add(l);
            if (spare.contains(l)) { // 잃어버린 학생 자신이 여분의 체육복이 있는 경우
                stolen.remove(l);
                spare.remove(l);
            } else if (spare.contains(l - 1)) { // 잃어버린 학생의 앞 번호 학생이 여분의 체육복이 있는 경우
                stolen.remove(l);
                spare.remove(l - 1);
            } else if (spare.contains(l + 1)) { // 잃어버린 학생의 뒷 번호 학생이 여분의 체육복이 있는 경우
                stolen.remove(l);
                spare.remove(l + 1);
            }
        }
        return n - stolen.size();
    }
}

나의 코드

소요 시간: 38분
시간 복잡도: $O(nlogn)$

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> spare = new HashSet<>(); // 여벌 체육복을 가지고 있는 학생
        for (int r : reserve) {
            spare.add(r);
        }
        
        Arrays.sort(lost);
        Set<Integer> stolen = new HashSet<>(); // 체육복을 도둑맞은 학생
        for (int l : lost) {
            stolen.add(l);
            if (spare.contains(l)) { // 잃어버린 학생 자신이 여분의 체육복이 있는 경우
                stolen.remove(l);
                spare.remove(l);
            }
        }
        for (int l : lost) {
              if (spare.contains(l - 1)) { // 잃어버린 학생의 앞 번호 학생이 여분의 체육복이 있는 경우
                stolen.remove(l);
                spare.remove(l - 1);
            } else if (spare.contains(l + 1)) { // 잃어버린 학생의 뒷 번호 학생이 여분의 체육복이 있는 경우
                stolen.remove(l);
                spare.remove(l + 1);
            }
        }
        return n - stolen.size();
    }
}

AI 코드

시간 복잡도: $O(n)$
코드 분석
학생 번호를 인덱스로 사용한 배열을 사용하여
Arrays.sort() 의 정렬 과정을 없앴다.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] clothes = new int[n + 2];
        for (int i = 1; i <= n; i++) clothes[i] = 1;
        for (int l : lost) clothes[l]--; // 체육복을 잃어버린 학생
        for (int r : reserve) clothes[r]++; // 여분의 체육복이 있는 학생
        
        for (int i = 1; i <= n; i++) {
            if (clothes[i] != 0) continue;
            if (clothes[i - 1] == 2) {
                clothes[i - 1]--;
                clothes[i]++;
            } else if (clothes[i + 1] == 2) {
                clothes[i + 1]--;
                clothes[i]++;
            }
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (clothes[i] == 0) cnt++;
        }
        return n - cnt;
    }
}

문제 풀이 후기

2차 실행 오류에서 실패 원인을 찾지 못했다.
체육복을 잃어버린 학생 중 본인이 여분의 체육복을 가지고 있는 경우를
가장 먼저 생각한 후, 앞사람 → 뒷사람 순서로 빌려주어야 한다.
설계는 맞았으나 구현에 있어서 구멍이 생겼다.