16. 프로그래머스 - 체육복 (그리디)

문제 설명

점심시간에 도둑이 들어 일부 학생들의 체육복이 도난당했습니다.
다행히 여벌 체육복이 있는 학생들이 일부 있어서, 이들이 도난당한 학생들에게 체육복을 빌려주려고 합니다.

• 학생들은 1번부터 번호가 매겨져 있고, 번호는 체격 순으로 되어 있습니다.
• 체육복을 빌려줄 수 있는 조건은 자기 바로 앞번호 또는 바로 뒷번호 학생에게만입니다.
  • 예: 4번 학생은 3번 또는 5번 학생에게만 체육복을 빌려줄 수 있습니다.
• 체육복이 없는 학생은 체육 수업에 참여할 수 없습니다.

이때, 적절히 체육복을 빌려줘서 체육 수업을 들을 수 있는 학생의 최대 수를 구해야 합니다.

---

입력

다음 세 가지 정보가 주어집니다:

• n: 전체 학생 수 (2 이상 30 이하의 정수)
• lost: 체육복을 도난당한 학생들의 번호가 담긴 정수 배열 (1 이상 n 이하, 중복 없음)
• reserve: 여벌 체육복을 가지고 있는 학생들의 번호가 담긴 정수 배열 (1 이상 n 이하, 중복 없음)

단, 여벌이 있지만 본인 체육복이 도난당한 경우,
자기 수업을 들을 수는 있지만 남에게 빌려줄 수는 없습니다.

---

출력

체육 수업을 들을 수 있는 학생의 최댓값을 정수로 반환합니다.

---

예시

nlostreservereturn

5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

 

---

예시 설명

예제 1

• 1번 학생 → 2번에게 빌려줌
• 3번 학생 or 5번 학생 → 4번에게 빌려줌
• 결과: 5명 모두 수업 가능

예제 2

• 3번 학생은 2번 또는 4번에게 빌려줄 수 있음 → 1명만 빌려줌
• 결과: 총 4명 수업 가능

---

접근 방식

일단 체육복을 빌릴 수 있으면 도난 당한 학생들은 체육복을 빌려서 최대한 많은 학생이 수업을 듣게 하는 문제이다.

 

이 풀이는 그리디 전략으로 풀 수 있다.

 

• lost와 reserve에서 겹치는 학생을 먼저 제거
  • 이들은 체육복 1벌만 갖고 있으므로 빌려줄 수도, 빌릴 필요도 없음
• lost 배열을 오름차순 정렬
  • 빌릴 수 있는 순서에 영향을 주므로 정렬은 필수
• lost 배열을 순회하며, reserve 배열에서 l-1 또는 l+1이 있으면 빌림
  • 한 번 빌려주면 reserve에서 제거
• n - 실제 체육복 없는 학생 수가 정답

위와 같이 접근하면 쉽게 생각하고 풀 수 있다.

 

알고리즘 코드

 

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Set<Integer> lostSet = new HashSet<>();
        Set<Integer> reserveSet = new HashSet<>();
        
        Arrays.sort(lost);
        
        for(int l : lost) {
            lostSet.add(l);
        }
        
        for(int r : reserve) {
            if(lostSet.contains(r)) {
                lostSet.remove(r);
            }else {
                reserveSet.add(r);
            }
        }
        
        for(int l : lost) {
            if(lostSet.contains(l)) {
                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);
                }
            }
        }
        
        return n - lostSet.size();
    }
}

 

 

Arrays.sort를 통해 lost 배열에 담긴 학생 번호를 정렬해주고 그 후 forEach문을 통해 잃어버린 학생들을 Set에 담고

체육복을 도난 당했지만 여분의 체육복이 있는 학생들은 lostSet에서 지워주면 되고 lostSet에 포함되지 않고 여분의 체육복이 있는 학생의 경우는 reserveSet에 담아주면 된다. 

 

이제 마지막 for문에서는 체육복을 잃어버린 한 학생을 기준으로 왼쪽 학생과 오른쪽 학생이 여분의 체육복을 가지고 있다면 reserveSet에서 왼쪽 학생을 지워주고 기준이 되는 학생을 lostSet에서 지워주면 된다. 

 

그 후 전체 학생 수 - 잃어버린 학생 수를 return해주면 된다.

 

시간 복잡도 분석

전체 시간 복잡도: O(N) (N은 lost.length + reserve.length 수준)이다.