체육복_복습

하이솝·2026년 9월 7일
Level 1greedy프로그래머스

2026.09.07

문제 풀이

1차 실행 오류

60.0/100

실패

실패 원인 분석

뒷번호 학생에게 먼저 옷을 빌렸을 경우,
뒤에 있는 학생이 옷을 빌리지 못할 수 있으므로 앞번호 학생에게 먼저 빌려야 함

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> spare = new HashSet<>(); // 여벌옷이 있는 학생들을 저장할 HashSet
        
        for (int r : reserve) { // 여벌옷이 있는 학생을 저장
            spare.add(r);
        }
        
        for (int l : lost) { // 여벌옷을 가진 학생 중 옷을 잃어버린 학생 제외
            if (spare.contains(l)) {
                spare.remove(l);
            }
        }
        for (int i = 0; i < lost.length; i++) {
            if (spare.contains(lost[i] + 1)) { 
            // 옷을 잃어버린 학생의 뒷번호 학생이 여벌옷이 있을 때
                spare.remove(lost[i] + 1);
            }
            else if (spare.contains(lost[i] - 1)) { 
            // 옷을 잃어버린 학생의 뒷번호 학생이 여벌옷이 있을 때 
                spare.remove(lost[i] - 1);
            }
            else {
                n--;
            }
        }
        
        return n;
    }
}

2차 실행 오류

63.3/100

실패

실패 원인 분석

옷을 잃어버린 학생 중 여벌옷을 가진 학생을 spare에서 제외 후,
아래 forEach 문에서 다시 반복했음

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> spare = new HashSet<>(); // 여벌옷이 있는 학생들을 저장할 HashSet
        
        for (int r : reserve) { // 여벌옷이 있는 학생을 저장
            spare.add(r);
        }
        
        for (int l : lost) { // 여벌옷을 가진 학생 중 옷을 잃어버린 학생 제외
            if (spare.contains(l)) {
                spare.remove(l);
            }
        }
        for (int l : lost) {
            if (spare.contains(l - 1)) { 
            // 옷을 잃어버린 학생의 앞번호 학생이 여벌옷이 있을 때
                spare.remove(l - 1);
            }
            else if (spare.contains(l + 1)) { 
            // 옷을 잃어버린 학생의 뒷번호 학생이 여벌옷이 있을 때 
                spare.remove(l + 1);
            }
            else {
                n--;
            }
        }
        
        return n;
    }
}

3차 실행 오류

90.0/100

실패

실패 원인 분석

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> spare = new HashSet<>(); // 여벌옷이 있는 학생들을 저장할 HashSet
        
        for (int r : reserve) { // 여벌옷이 있는 학생을 저장
            spare.add(r);
        }
        
        for (int l : lost) {
            if (spare.contains(l)) {
                spare.remove(l);
            }
            else if (spare.contains(l - 1)) { 
            // 옷을 잃어버린 학생의 앞번호 학생이 여벌옷이 있을 때
                spare.remove(l - 1);
            }
            else if (spare.contains(l + 1)) { 
            // 옷을 잃어버린 학생의 뒷번호 학생이 여벌옷이 있을 때 
                spare.remove(l + 1);
            }
            else { // 옷을 빌릴 수 없을 때
                n--;
            }
        }
        
        return n;
    }
}

4차 실행 오류

93.3/100

실패

실패 원인 분석

reseve, 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<>(); // 여벌옷이 있는 학생들을 저장할 HashSet
        Set<Integer> temp = new HashSet<>(); // 여벌옷이 있고, 도난을 당한 학생들을 저장할 HashSet
        
        for (int r : reserve) { // 여벌옷이 있는 학생을 저장
            spare.add(r);
        }
        
        for (int l : lost) { // 여벌옷을 가지고 있으면서 도난당한 학생 제외
            if (spare.contains(l)) {
                spare.remove(l);
                temp.add(l);
            }
        }
        
        for (int l : lost) {
            if (temp.contains(l)) { // 여벌옷을 이미 본인에게 사용한 학생일 때
                continue;
            }
            if (spare.contains(l - 1)) { 
            // 옷을 잃어버린 학생의 앞번호 학생이 여벌옷이 있을 때
                spare.remove(l - 1);
            }
            else if (spare.contains(l + 1)) { 
            // 옷을 잃어버린 학생의 뒷번호 학생이 여벌옷이 있을 때 
                spare.remove(l + 1);
            }
            else { // 옷을 빌릴 수 없을 때
                n--;
            }
        }
        
        return n;
    }
}

나의 코드

소요 시간: 49분
시간 복잡도: O(nlogn)O(n log n)

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(reserve);
        Arrays.sort(lost);
        
        Set<Integer> spare = new HashSet<>(); 
        // 여벌옷이 있는 학생들을 저장할 HashSet
        Set<Integer> temp = new HashSet<>(); 
        // 여벌옷이 있으면서 도난을 당한 학생들을 저장할 HashSet
        
        for (int r : reserve) { // 여벌옷이 있는 학생을 저장
            spare.add(r);
        }
        
        for (int l : lost) { // 여벌옷을 가지고 있으면서 도난당한 학생 제외
            if (spare.contains(l)) {
                spare.remove(l); // 여벌옷 제거
                temp.add(l); // 여벌옷을 가지고 있으면서 도난당한 학생 저장
            }
        }
        
        for (int l : lost) {
            if (temp.contains(l)) { // 여벌옷을 이미 본인이 입은 학생일 때
                continue;
            }
            if (spare.contains(l - 1)) { 
            // 옷을 잃어버린 학생의 앞번호 학생이 여벌옷이 있을 때
                spare.remove(l - 1);
            }
            else if (spare.contains(l + 1)) { 
            // 옷을 잃어버린 학생의 뒷번호 학생이 여벌옷이 있을 때 
                spare.remove(l + 1);
            }
            else { // 옷을 빌릴 수 없을 때
                n--;
            }
        }
        
        return n;
    }
}

AI 코드

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

코드 분석

int 배열을 이용해서 각 학생 번호를 인덱스로,
각 학생에 대해 여벌옷을 가지고 있으면 2, 도난당하지 않았다면 1,
도난당한 학생의 경우에는 0이지만, 도난당하고 본인의 여벌옷을 입은 학생의 경우
자동으로 1이 된다.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] clothes = new int[n + 2];        // 1~n 사용, i+1 접근 대비 +2
        for (int i = 1; i <= n; i++) clothes[i] = 1;
        for (int l : lost)    clothes[l]--;
        for (int r : reserve) clothes[r]++;

        int answer = 0;
        for (int i = 1; i <= n; i++) {         // 번호 순회 = 자동으로 오름차순
            if (clothes[i] == 0) {
                if (clothes[i - 1] == 2) { clothes[i - 1]--; clothes[i]++; }
                else if (clothes[i + 1] == 2) { clothes[i + 1]--; clothes[i]++; }
            }
            if (clothes[i] >= 1) answer++;
        }
        return answer;
    }
}

문제 풀이 후기

AI 코드를 보면 전부터 항상 느끼는 바가 있다.
배열의 사용을 엄청나가 다양하게 생각하지 못한 방식으로 사용한다.

HashSet이나 Arrays를 이용한 정렬 등을 사용하지 않는다.
단순한 배열로 해결하는게 항상 신기하고 나도 이런 코드를 짤 수 있는 것을 목표로 코딩 테스트 공부를 해야겠다.

4차 실행 오류에서 도저히 원인을 찾을 수 없어서
프로그래머스의 질문하기 탭으로 들어가서 게시물을 탐색하던 중
정렬이 이뤄지지 않음을 발견함과 동시에 실패..

profile
하이솝
이전 포스트

전력망을 둘로 나누기_복습

다음 포스트

조이스틱_복습

0개의 댓글