[프로그래머스] 체육복 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

코딩테스트 고득점 Kit > 탐욕법(Greedy)

체육복 | 문제 바로가기

문제풀이 (2022-01-25 TUE 💻)

🤔 사담

개인적으로 Level1인게 정말 킹받았던 문제..
은근 놓치면 안 되는 조건들도 있고 개인적으로 꽤나 까다롭게 느껴졌다 ㅠㅠ

⭐ 풀이의 핵심

• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

👉 위의 조건을 간과하지 않는 것이 중요한 포인트이다.
해당 학생은 체육 수업을 들을 수는 있지만 체육복을 빌려줄 수는 없는 학생이므로,
탐색에 앞서 lost와 reserve에서 각각 해당 학생을 삭제해주고,
answer에 해당 학생의 수를 포함해주는 작업이 필요하다.

👉 체육복을 도난 당한 학생들은 각자 최대 2명에게 체육복을 빌릴 수 있다.
따라서 총 2회의 탐색을 진행하며 최대한 많은 학생들이 체육 수업을 듣기 위해서
1회차 탐색 시에는 2명에게 체육복을 빌릴 수 있는 학생들은 일단 넘어가고
체육복을 1명에게만 빌릴 수 있는 학생들에게 우선적으로 체육복을 빌려준다.
2회차 탐색 시에는 체육복을 빌릴 수 있는 남은 학생들에게 체육복을 빌려준다.

🚨 간과 또는 실수한 부분

👉 여벌 체육복을 가져왔다가 체육복을 도난 당한 학생에 대해 처리하는 부분을 여러 번 고쳤다.

✔ 처음에는 while 문 밖에서 answer += n-lost.size() 라고 answer 값을 업데이트하고
while 문 안의 for 문에서
find(reserve.begin(), reserve.end(), lost[i]) != reserve.end()일 경우를 체크했는데

• answer에 해당 학생의 수를 포함해주는 것을 깜빡
• while 문 안의 for 문에서 해당 부분을 처리할 경우
  ex) vector<int> lost = { 2, 3 } vector<int> reserve = { 3 } 과 같은 경우
  3번 학생이 2번 학생에게 체육복을 빌려줄 수 없는데
  for문은 앞쪽부터 순차적으로 돌기 때문에
  2번 학생도 3번 학생도 체육 수업을 들을 수 있게,
  즉 체육복을 빌려줄 수 없게 된 학생이 체육복을 빌려준 것으로,
  잘못 처리되는 문제를 발견

하였다

✔ 그래서 아래의 코드와 같이 아예 while문 이전,
그리고 answer += n-lost.size() 업데이트 이전에 해당 학생들을 처리하도록 수정했다
하지만 이 부분에서는 또

• 해당 학생을 i=0 부터 reserve.size()-1 까지 for문을 돌며
  reserve[i] 값이 lost 벡터에 존재하는지 확인하는데
  만약 해당 학생이 존재하여 reserve에서 삭제할 경우
  reserve 벡터에서 인덱스가 i보다 크거나 같은 원소들은 인덱스가 하나씩 앞당겨지므로
  i--를 해주고 탐색을 계속 해나가야 한다는 것을 깜빡

하여 답이 이상하게 나오기도 했다.. 😭

🔽 코드 (C++)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;

    /* cf) 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다.
    이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다. */
    for (int i=0; i<reserve.size(); i++) {
        auto lostIter = find(lost.begin(), lost.end(), reserve[i]);
        if (lostIter != lost.end()) {
            reserve.erase(reserve.begin()+i); // 체육복을 빌려줄 수는 없지만
            lost.erase(lostIter); // 체육수업을 들을 수는 있음
            i--;
        }
    }

    int lostN = lost.size();
    answer += n-lostN;

    /* 총 2회 탐색
    1회차 탐색 시에는 체육복을 1명에게만 빌릴 수 있는 학생들에게 우선적으로 체육복을 빌려줌 */
    int turn = 0;
    while (turn < 2) {
        for (int i=0; i<lostN; i++) {
            auto left = find(reserve.begin(), reserve.end(), lost[i]-1);
            auto right = find(reserve.begin(), reserve.end(), lost[i]+1);
            if (left == reserve.end() && right == reserve.end()) { // 체육복을 빌릴 수 없는 경우
                continue;
            }
            if (turn == 0 && left != reserve.end() && right != reserve.end()) { // 1회차 탐색 + 체육복을 2명에게 빌릴 수 있는 경우
                continue;
            }
            else if (left != reserve.end()) { // 앞번호의 학생에게 빌릴 수 있는 경우
                reserve.erase(left);
                answer++;
            }
            else { // 뒷번호의 학생에게 빌릴 수 있는 경우
                reserve.erase(right);
                answer++;
            }
        }
        turn++;
    }
    
    return answer;
}