lv1 체육복 [다시]

https://school.programmers.co.kr/learn/courses/30/lessons/42862#

프로그래머스

 

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        //lost, reverse 정렬
        //lost set 순서 유지해
        //lost.contains[reserve[idx]] == true , answer++
        //답 n - lost.size() + answer
        
        LinkedHashSet<Integer>lostSet = new LinkedHashSet<Integer>();
        LinkedHashSet<Integer>reserveSet = new LinkedHashSet<Integer>();
        Arrays.sort(lost);
        Arrays.sort(reserve);
        for(int idx = 0; idx < lost.length; ++idx){
            lostSet.add(lost[idx]);
        }
        for(int idx = 0; idx < reserve.length; ++idx){
            reserveSet.add(reserve[idx]);
        }
        
        //동일 값은 별도 진행(체육 여분 있는 사람 = 체육 도난 당한 사람)
        for(int a : reserve){
            if(lostSet.contains(a)){
                answer++;
                reserveSet.remove(a);
                lostSet.remove(a);
            }
        }

        // a 를 여기에 한번에 삭제하면, 오름차순으로 접근하다보니
        // 자신의 여분을 입기 전에 다른 번호가 낮은 학생이 가로챔.
        //n : 5 , lost [4, 5, 7]  reserve [3, 4, 6] 
        //답은 5- 3 + 2  = 4가 되야하나
        //3이 4를 , 4가 5를, 6이 7로 여분을 주는 잘못된 로직으로 갈 시
        // 5 - 3 + 3 = 5가 된다.
        //그렇기에 별도로 l의 4와 r의 4 즉 자신의 옷이 도난 당했으나 여벌을 입으려고 별도로 로직처리.
        for(int a : reserveSet){
            if(lostSet.contains(a-1)){
                lostSet.remove(a-1);
                answer++;
            }
            else if(lostSet.contains(a+1)){
                lostSet.remove(a+1);
                answer++;
            }
        }
        
        return answer;
    }
}

 

 

 

 

 

타인코드

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;

        for (int l : lost) 
            people[l-1]--;
        for (int r : reserve) 
            people[r-1]++;

        for (int i = 0; i < people.length; i++) {
            if(people[i] == -1) {
                if(i-1>=0 && people[i-1] == 1) {
                    people[i]++;
                    people[i-1]--;
                }else if(i+1< people.length && people[i+1] == 1) {
                    people[i]++;
                    people[i+1]--;
                }else 
                    answer--;
            }
        }
        return answer;
    }
}

핵심 아이디어: 학생 상태를 숫자로 표현

 

 

java

int[] people = new int[n];  // 모든 학생 0으로 초기화

값	의미
0	평범한 학생 (체육복 1개)
-1	도난당한 학생 (체육복 0개)
+1	여벌 있는 학생 (체육복 2개)
둘 다 해당	-1 + 1 = 0 → 자기 자신 처리 자동완성

 

 

java

for (int l : lost)   people[l-1]--;   // 도난 → -1
for (int r : reserve) people[r-1]++;  // 여벌 → +1
// 둘 다면 0이 되어 자동으로 "빌려줄 수 없음" 처리

---

순회 로직

 

java

if(people[i] == -1) {           // 이 학생이 체육복 없음
    if(people[i-1] == 1) {      // 앞 학생이 여벌 있으면
        people[i]++;             // -1 → 0 (해결)
        people[i-1]--;           // 1 → 0 (빌려줌)
    } else if(people[i+1] == 1) { // 뒷 학생이 여벌 있으면
        people[i]++;
        people[i+1]--;
    } else answer--;             // 못 빌리면 수업 못 들음
}

앞을 먼저 확인하는 이유: i를 왼쪽→오른쪽으로 순회하므로, 앞(i-1)은 이미 처리 완료된 학생입니다. 앞 학생이 여벌이 있다면 지금 안 쓰면 영원히 못 씁니다.

---

예제 추적

n=5, lost=[2,4], reserve=[1,3]

초기화 후 people: [1, -1, 1, -1, 0]

 

i	people[i]	행동	people 변화
0	1	스킵	-
1	-1	i-1=0이 1 → 앞에서 빌림	[0, 0, 1, -1, 0]
2	1	스킵	-
3	-1	i-1=2이 1 → 앞에서 빌림	[0, 0, 0, 0, 0]
4	0	스킵	-

answer = 5