[프로그래머스] 체육복 (Lv.1)
문제 링크
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.
체육복이 없으면 체육수업을 들을 수 없어서 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있습니다. 이 때 이 학생은 체육복을 하나밖에 없으므로 다른 학생에게는 체육복을 빌려줄 수 없습니다.
내 풀이
전처리 단계와 대여 단계로 나눠서 풀었다.
전처리 단계: reserve를 순회하며 lost에 같은 번호가 있으면 해당 학생은 자기 여벌을 직접 쓰는 것으로 처리해 lost에서 제거한다. 이 학생은 다른 사람에게 빌려줄 수 없으므로 filtered_reserve에 추가하지 않는다. lost에 없는 학생만 filtered_reserve에 추가해 순수하게 빌려줄 수 있는 학생 목록을 만든다.
대여 단계: filtered_reserve의 각 학생이 번호 ±1인 학생에게 빌려줄 수 있는지 확인한다. 앞번호(r-1) 우선으로 찾고, 없으면 뒷번호(r+1)를 찾아 lost에서 제거한다.
최종적으로 n - lost.size()를 반환하면 체육복이 있는 학생 수가 된다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
sort(lost.begin(), lost.end());
sort(reserve.begin(), reserve.end());
vector<int> filtered_reserve;
for(int r : reserve)
{
auto it = find(lost.begin(), lost.end(), r);
if(it != lost.end())
lost.erase(it);
else
filtered_reserve.push_back(r);
}
reserve = filtered_reserve;
for(int r : reserve)
{
auto it = find(lost.begin(), lost.end(), r - 1);
if(it == lost.end())
it = find(lost.begin(), lost.end(), r + 1);
if(it != lost.end())
lost.erase(it);
}
return n - (int)lost.size();
}
시간복잡도 분석
- 정렬: O(L log L + R log R) — L = lost 크기, R = reserve 크기
- 전처리 루프: reserve 각 원소마다 find(O(L)) → O(R × L)
- 대여 루프: reserve 각 원소마다 find 최대 2회(O(L)) → O(R × L)
- 전체: O(R × L)
제한사항에서 n ≤ 30이므로 L, R ≤ 30. 최악의 경우 30 × 30 = 900번 연산으로 충분히 통과 가능하다.
오답노트
처음 제출 시 83.3%가 나왔다.
원인은 lost와 reserve에 동시에 존재하는 학생을 처리하지 않은 것이었다. 예를 들어 lost=[2,4], reserve=[2,3]일 때, 2번 학생은 도난당했지만 여벌도 있으므로 자기 것을 쓰면 된다. 그런데 이 처리 없이 그냥 진행하면 3번 학생이 2번에게 빌려주게 되고, 정작 4번 학생은 아무도 빌려주지 못하는 문제가 생겼다.
수정하는 과정에서도 실수가 있었다. for(int r : reserve) 루프 안에서 reserve.erase(it)를 시도했는데, it가 lost의 이터레이터였고, 순회 중인 컨테이너를 직접 수정하면 UB가 발생한다. filtered_reserve를 별도로 만들어 순회 중 수정 없이 처리하는 방식으로 해결했다.
후기
탐욕법을 들어만 봤지, 제대로 공부하고 응용해본 것은 오늘이 처음이었다. 사실 아직까지는 어떤 문제가 탐욕이 적용 가능한지 구별해낼 자신은 없지만, 하다보면 늘 거라고 생각한다.