체육복

프로그래머스 - 체육복

문제 요약

---

• 여벌 체육복이 있는 학생이 체육복을 빌려줄 수 있음.
• 바로 앞번호의 학생이나 뒷번호의 학생에게만 빌려줄 수 있다 !
• 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야한다.

제한사항

---

• 2 ≤ n (전체 학생의 수) ≤ 30
• 1 ≤ lost (체육복 도난 당한 학생의 수) ≤ n (중복 X)
• 1 ≤ reserve (여벌 체육복이 있는 학생의 수) ≤ n (중복 X)
• 여벌 체육복이 있는 학생만 다른 학생에게 빌려줄 수 있다 !
  → 여벌 체육복이 있는 학생이 도난 당하면 빌려줄 수 없다.

💡Idea

1. answer 초기값은 n - lost.size() 으로 한다.
   → 도난 당한 학생을 제외한 학생은 수업을 들을 수 있기 때문
2. 도난 당한 학생의 번호를 어떻게 저장할까 ?
   → reserve를 돌면서 도난당한 학생인지 탐색할 수 있어야하므로 key값을 가지는 map 생성
3. 빌려주는 과정을 어떻게 처리할 것인가 ?
   ① 우선 도난당했는지 확인하자 !
   ② 도난당하지 않았다면 앞, 뒷번호 학생 확인
   → 많은 학생한테 빌려주기 위해서는 앞번호 학생을 먼저 빌려주자. (뒷번호 학생은 다음 학생의 앞번호로 빌려줄 수 있기 때문)
   → 앞번호 학생한테 빌려줄 수 없다면 뒷번호 학생한테 빌려주기.
4. answer을 언제 증가시키지 ?
   → reserve와 lost 둘 다 존재할 경우
   (빌리지 않아도 체육복이 있기 때문)
   → 여벌 체육복이 있는 학생이 앞번호나 뒷번호 학생에게 빌려줄 경우

[ SourceCode ]

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    map <int, int> map; // 도난 당한 학생 리스트
   
    sort(lost.begin(), lost.end()); // 정렬
    sort(reserve.begin(), reserve.end()); // 정렬
   
    for(int i=0; i<lost.size(); i++) {
        if(find(reserve.begin(), reserve.end(), lost[i]) == reserve.end()) {
            map.insert(make_pair(lost[i], 1));
        }
        else {
            reserve.erase(find(reserve.begin(), reserve.end(), lost[i]));
        }
    }
   
    int answer = n - map.size(); // 전체 학생 수 - 도난 당한 학생 수
   
    for(int i=0; i<reserve.size(); i++) { // 여벌 있는 학생 수 만큼
        if(reserve[i] - 1 > 0 && map[reserve[i] - 1]) {
            map.erase(reserve[i] - 1);
            answer++;
        }
        else if(reserve[i] + 1 <= n && map[reserve[i] + 1]) {
            map.erase(reserve[i] + 1);
            answer++;
        }
    }
   
    return answer;
}

Feedback

---

1. 처음에 도난 당한 학생 중 여벌 체육복이 있는 학생을 빼주지 않았다.
   → 반례를 찾기 힘들었는데 반례로는 n = 3, lost = [2, 3], reserve = [1, 2]가 있었다.
   → 이 경우 1번 학생이 2번 학생에게 체육복을 빌려주게 되는데, 2번 학생은 빌릴 필요가 없다.
   ∴ 도난 당했으면서 여벌 체육복이 있는 학생은 제거해주는 작업이 필요하다 !

2. 조건을 잘 생각해보며 제거할 필요가 있는지 확인해보는 습관 가지기 ✨