[Java] 프로그래머스 : 체육복

[Java] 프로그래머스 : 체육복

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

프로그래머스

---

접근

'여벌 체육복을 가져온 학생이 도난 당했을 경우를 가정하고, 이 학생은 다른 학생들에게 체육복을 빌려줄 수 없다.'

lost와 reserve에 동시에 존재하는 학생인 경우, 결국 체육복이 하나뿐이므로 자기만 입을 수 있다는 말이다.

 

n= 6, lost = [6, 4, 2], reserve = [1, 4, 5], return = 5이다.

이때 4가 위의 케이스에 해당하므로 lost도 아니고 reserve도 아닌, 자기 자신만 입을 수 있는 상태가 되는 것이다.

따라서 양쪽에서 4를 제거하면 다음과 같다.

 

lost = [6, 2], reserve = [1, 5]

위와 같이 양쪽이 오름차순으로 정렬되지 않은 케이스의 경우, 두 리스트를 오름차순 정렬한 뒤 나머지 처리를 해주어도 되지만, 

해시맵을 활용하면 더 빠르게 구현할 수 있었다.

 

리스트에 특정 값을 넣는 방식으로 구현하려면 코드가 너무 길어지기 때문에 아래 방법들을 사용했다.

import java.util.HashSet;

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

        HashSet<Integer> resSet = new HashSet<>();
        HashSet<Integer> loSet = new HashSet<>();

        for(int i: reserve) {
            resSet.add(i);
        }

        for(int i: lost) {
            if(resSet.contains(i)) { res와 lost 모두 존재하는 경우 resSet에서 빼버리고 loSet에도 넣지 않는다.
                resSet.remove(i);
            }
            else {
                loSet.add(i);
            }
        }

        for(int i: resSet) {
            if(loSet.contains(i-1)) {
                loSet.remove(i - 1);
            }
            else if(loSet.contains(i+1)) {
                loSet.remove(i + 1);
            }
        }   

        answer = n - loSet.size();

        return answer;
    }
}

 

 

단순 배열만 사용하는 방식으로도 문제를 풀이할 수 있었다.

lost의 경우 -1처리를, reserve의 경우 +1처리를 한다.

여벌 체육복을 가져온 학생이 도난 당한 경우, 해당 학생은 0이 되어, 자신의 체육복만 소지한 상태가 된다.

특정 학생이 -1일때, 자신의 앞 뒤로 1의 값을 가지고 있는 학생에게 체육복을 빌려온다.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        int[] students = new int[n];
        
        for (int l : lost) {
            students[l-1]--;
        }
        for (int r : reserve) {
            students[r-1]++;
        }
        // -1를 가진 학생은 lost상태이므로 1을 가진 학생에게서만 체육복을 빌려올 수 있다.
        
        for (int i = 0; i < n; i++) {
            if (students[i] == -1) { // 체육복이 없는 학생이 있을 때
                if ( i-1 >= 0 && students[i-1] == 1 ) { // 그 앞에 애가 체육복이 있으면 빌려오기
                    students[i]++;
                    students[i-1]--;
                }
                else if ( i+1 < students.length && students[i+1] == 1 ) {// 그 뒤에 애가 체육복 있으면 빌려오기
                    students[i]++;
                    students[i+1]--;
                }
                else {
                    answer--;
                }
            }
        }
        
        return answer;
    }
}