[알고리즘] 체육복

My Github Repository for Solution Code

[level 1] Title: 체육복, Time: 8.62 ms, Memory: 68.7 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@2c90b2d

 

Problem Source

프로그래머스

 

Key Takeaways

1. 여벌옷을 가져온 그룹, 잃어버린 그룹을 Set으로 변환하여 여벌옷을 가져왔으면서 잃어버린 학생 제거

2. 최악의 경우의 수(여벌옷을 가져온 그룹이 모두 옷을 잃어버린 경우)에서 시작

3. 마지막에 잃어버린 그룹에서 학생들을 번호순으로 순회하므로 최초에 Set 변환 시 정렬한 점(매우 중요)

Guidelines
1. Always include reasons for choosing certain approach/technology/framework/technique, etc.
2. Before writing a code, summarize the plan in 3 lines, including but not limited to:
- What data structures are we using?
- Time / Space complexity
- What are the edge cases?

3. Always leave reasons for failures to find patterns in mistakes. It is helpful in recognizing my weaknesses.
4. Don't cling to a problem that takes more than 30 minutes to solve. Check the answer first, and come back to days later.
  4-1. After you understood the answer, make it yours.
5. When you solved a problem without knowking how you did it, and it occurs repeatedly, it's time to take a step back and grind on one problem. 

Problem

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

My Solution

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        
        // 최악의 경우 (잃어버린 학생들 모두 여벌옷이 없을 때)에서 시작
        int answer = n - lost.length;
        
        // lost, reserve를 각각 set으로 변환
        // Java 8 이상의 Stream API
        Set<Integer> lostCopy = Arrays.stream(lost)
            .boxed()
            .sorted() // 추가
            .collect(Collectors.toSet());
        
        Set<Integer> reserveCopy = Arrays.stream(reserve)
            .boxed()
            .collect(Collectors.toSet());
        
        // 여벌옷을 가져왔으면서 잃어버린 학생들 추리기
        // reserveCopy에서도 삭제
        for(int res : reserve) {
            if(lostCopy.contains(res)) {
                answer++;
                lostCopy.remove(res);
                reserveCopy.remove(res);
                continue;
            }
        }
        
        // lostCopy에 남은 학생들과 reserveCopy에 남은 학생들을 비교하여 추가 생존자 구하기
        for(int loser : lostCopy) {
            if(reserveCopy.contains(loser-1)) {
                answer++;
                reserveCopy.remove(loser-1);
                continue;
            }
            if(reserveCopy.contains(loser+1)) {
                answer++;
                reserveCopy.remove(loser+1);
                continue;
            }
        }

        return answer;
    }
}
/*
번호가 체격순 -> 1번이 2번보다 크다면, 2번은 3번보다 반드시 크다.
목표 : 최대한 많은 학생이 체육복을 입는 것.
reserve 배열 내 번호와 lost 배열 내 번호가 겹칠 수 있다. 이 경우 여벌의 체육복을 가져왔지만 도난당했으므로 빌려줄 수 없다.
힌트 : 그리디 알고리즘 (모든 경우의 수를 순회)
*/
/* 접근
최악의 경우, lost에 포함된 학생들이 reserve에 포함된 학생들 중 어느 누구로부터도 빌리지 못하는 경우 -> answer = n - lost.length;

목표는 최댓값을 구하는 것이므로 answer가 증가하는 조건 파악
1) 자기 자신에게 빌려주는 경우 (reserve이면서 lost 동시에 존재, 자신이 우선)
2) 인접한 타인에게 빌려주는 경우 (reserve에 있는 원소 중 lost에 없으면서 자기 자신과 번호가 인접해야 함)

역발상 : lost가 아니라 reserve를 순회하자.
reserve를 순회하며 lostSet에 있으면 answer 1 증가, lostSet.remove() 실행
남은 lostSet으로 reserve 내 원소를 순회하면서 추가로 빌리기

reserve의 원소를 복사한 동적 집합 생성(Set<Integer> reserveCopy)
lost의 원소를 두 번 순회
1회차 -> lost이면서 reserve 동시에 있는 학생들 추리기
lost의 원소를 작은 수부터 순회, 자기 자신, 직전 원소 또는 직후 원소가 reserveCopy에 있는지 확인. 자기 자신이 있다면 빌릴 필요가 없으므로 reserveCopy에서 자기 자신을 삭제하고 skip
자기 자신이 없다면 직전 원소를 우선, 없다면 직후 원소를 선택한 뒤 현재 체육복을 가져온 사람 수 1 증가 (k = 4)
이후 reserveCopy에서 선택된 원소 제거.
lost의 다음 원소로 이동, 반복
k 반환
*/

전체 로직 흐름

1. 기저값 설정: answer = n - lost.length — 아무도 못 빌리는 최악의 경우를 시작점으로 삼는 역발상이 깔끔합니다.
2. 자기 자신 처리 (1패스): reserve를 순회하며 lost와 겹치는 학생을 먼저 처리. 즉, 도난당했지만 여벌이 있는 학생은 answer++하고 양쪽 Set에서 모두 제거합니다.
3. 이웃 대여 처리 (2패스): 남은 lostCopy를 순회하며 loser-1 → loser+1 순으로 reserveCopy를 확인하고 대여합니다.

Efficiency

3. 시간복잡도

• Stream 변환: O(L + R) (L = lost 크기, R = reserve 크기)
• 1패스, 2패스: 각 O(L), O(R)
• 전체: O(n) 수준으로 매우 효율적입니다.

Strengths:

• 자기 자신 우선 처리를 1패스에서 완전히 분리한 것이 정확합니다. 이를 이웃 처리와 섞으면 엣지 케이스가 발생하는데, 여러 번의 오답 이후 이 구조로 정착한 점이 보입니다.
• Set 사용으로 포함 여부 확인(contains)과 삭제(remove)를 모두 O(1)에 처리한 것이 효율적입니다.
• 원본 배열을 건드리지 않고 Copy Set을 만들어 사용하는 방어적 코딩 습관이 좋습니다.
• 주석으로 접근 과정을 단계별로 기록한 점도 훌륭합니다.

 

Limitations (or Trade-offs):

1. for-each 중 Set 순서 비보장 문제

for(int loser : lostCopy) 에서 lostCopy는 HashSet이므로 순회 순서가 보장되지 않습니다. 이 문제는 loser-1을 우선하는 Greedy 전략을 쓰는데, 만약 lost = [3, 4], reserve = [2, 5] 같은 케이스에서 4번이 먼저 순회되면 5번을 써버리고, 3번은 2번을 쓰면 되니 문제없지만, 반대로 3번이 먼저 순회되어 2번을 쓰고, 4번은 5번을 써도 결과가 같습니다. 이 문제는 연속 번호 충돌 구조가 단순해서 현재 테스트 케이스에서는 통과되지만, 정확한 Greedy를 보장하려면 TreeSet(정렬된 Set)이나 정렬 후 순회하는 것이 더 안전합니다.

---

Lessons Learned

정확한 Greedy를 보장하기 위해선 정렬 후 순회가 필수적이다. 단순 HashSet은 순회 순서를 보장하지 않는다.
원본 배열을 건드리지 않고 Copy Set을 만들어 사용하는 방어적 코딩 습관은 플러스다.