[99클럽 코테 스터디] 20일차 TIL 그리디

 

 

오늘의 문제는 프로그래머스

 

체육복

 

 

문제

 

 

 

문제 설명 

 

체육 수업을 들을 수 있는 최대 학생 수를 반환하는 문제입니다. 

체육복이 없는 학생은 수업을 들을 수 없고, 일부 학생이 체육복을 도난당한 상황입니다. 

여분의 체육복이 있는 학생은 학생 번호의 바로 앞 번호 학생이나 바로 뒷 번호의 학생에게만 체육복을 빌려줄 수 있습니다. 

 

입력 

• 전체 학생 수 : n
• 체육복을 도난당한 학생들의 번호가 담긴 배열 : lost
• 여분의 체육복을 가진 학생들의 번호가 담긴 배열 reserve 

출력

• 체육 수업을 들을 수 있는 학생의 최댓값 

 

예를 들어 n = 5, lost = [2, 4], reserve = [1,3,5] 일 때 반환 값은 5입니다. 

 

 

 

 

문제 풀이 시간

권장 풀이 시간은 60분이었고, 저는 30분이 걸렸습니다.

 

 

 

 

문제 접근 방식

먼저 체육복을 잃어버린 학생과 여분의 체육복이 있는 학생의 번호를 각각 해쉬셋에 저장합니다. 둘의 교집합을 구해 중복된 학생 번호를 찾아 제거합니다. 

체육복을 잃어버린 학생 번호를 순회하며 앞 번호나 뒷 번호 학생이 여분의 체육복을 가지고 있는지 검사합니다. 만약 그렇다면 해당 학생의 체육복을 빌려주고 여분의 체육복을 가진 학생의 목록에서 제거합니다. 

마지막으로 전체 학생 수에서 체육복을 빌리지 못한 학생의 수를 뺀 뒤 결과를 반환합니다. 

 

 

 

문제 풀이

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        Set<Integer> lostSet = new HashSet<>();
        Set<Integer> reserveSet = new HashSet<>();
        
        for(int l : lost) {
            lostSet.add(l);
        }
        
        for(int r : reserve) {
            reserveSet.add(r);
        }
        
        Set<Integer> intersection = new HashSet<>(lostSet);
        intersection.retainAll(reserveSet);
        
        lostSet.removeAll(intersection);
        reserveSet.removeAll(intersection);
        
        for(int l : new HashSet<>(lostSet)) {
            if(reserveSet.contains(l - 1)) {
                reserveSet.remove(l - 1);
                lostSet.remove(l);
            } else if(reserveSet.contains(l + 1)) {
                reserveSet.remove(l + 1);
                lostSet.remove(l);
            }
        }
        
        answer = n - lostSet.size(); 
        
        return answer;
    }
}

 

 

HashSet 사용하기

해쉬셋은 데이터의 중복을 허용하지 않고 빠른 검색, 추가, 삭제가 가능한 컬렉션입니다. 내부적으로 해시 테이블을 사용해 데이터를 저장하기 때문에 특정 요소의 존재 여부를 빠르게 확인할 수 있습니다. 

 

 

 

HashSet 메서드 알아보기 

retainAll(collection) 는 해쉬셋의 요소들을 Collection 인자의 요소들과 비교해 동일한 요소는 해쉬셋에 남기고 그 외의 요소를 제거하는 메서드입니다. 즉 두 객체의 공통적인 요소는 해쉬셋에 남기고 그 외의 요소를 삭제하는 것입니다. 

문제 풀이에서는 두 집합 간의 교집합을 구하는데 사용하였습니다. lostSet과 reserveSet에 모두 포함된 학생들은 여분이 있지만 체육복을 도난당한 학생들이므로 이를 상쇄하여 제거하는데 사용했습니다. 

 

 

 

코드 개선하기

반복문에서 lostSet의 복사복을 만드는 대신 원래의 lostSet을 그대로 순회하도록 해서 불필요한 객체 생성을 줄였습니다. 

또한 체육복을 빌리지 못한 학생 수를 감소시켜 최종 반환값에 전체 학생 수에서 체육복을 빌리지 못한 학생 수를 빼는 연산을 제거했습니다. 대신 체육복을 입을 수 있는 학생 수를 직접 반환하도록 수정했습니다. 

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        
        Set<Integer> lostSet = new HashSet<>();
        Set<Integer> reserveSet = new HashSet<>();
        
        for(int l : lost) {
            lostSet.add(l);
        }
        
        for(int r : reserve) {
            reserveSet.add(r);
        }
        
        Set<Integer> intersection = new HashSet<>(lostSet);
        intersection.retainAll(reserveSet);
        
        lostSet.removeAll(intersection);
        reserveSet.removeAll(intersection);
        
        for (int l : lostSet) {
            if (reserveSet.contains(l - 1)) {
                reserveSet.remove(l - 1);
            } else if (reserveSet.contains(l + 1)) {
                reserveSet.remove(l + 1);
            } else {
                n--; 
            }
        }
        
        return n; 
    }
}

 

 

 

 

다른 풀이 알아보기 

아래 코드는 배열의 인덱스를 이용한 풀이입니다. 

people 배열에서 값이 1이면 여분이 있는 학생이고 -1이면 체육복이 없는 학생을 의미합니다. 반복문을 순회하며 앞이나 뒤 학생에게서 체육복을 빌릴 수 있는지 여부를 검사하고 불가능한 경우 학생수를 감소시켜 결과값을 반환하고 있습니다. 

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;
    }
}

 

 

 

 

 

 

이렇게 오늘 20일차 TIL을 작성해 보았습니다.