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

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

풀이

탐욕법을 사용해 해결하는 문제입니다. 여분 체육복을 가진 학생 또한 도난당할 수 있음에 유의합니다.

 

체육복을 잃어버린 경우 더 앞쪽 번호의 학생에게 빌려야 최대한 많은 학생이 수업을 들을 수 있습니다.

lost = [2, 4]

reserve = [1, 3] 

일 경우, 뒷쪽 학생에게 먼저 빌릴경우 4번 학생은 수업을 듣지 못하므로 최적해가 아닙니다.

 

따라서, 현재 잃어버린 학생 curr_lost의 바로 앞 학생이 reserve에 존재한다면 answer++를 해줍니다. 이때, 이미 빌려준 학생 처리는 -100으로 하여 1 또는 -1이 되는 것을 방지합니다.

앞쪽 학생이 없다면 뒷쪽 학생이 있는지 확인하고 빌리면 됩니다. 

 

여분 체육복을 가진 학생 또한 도난당할 수 있으므로, answer++ 및 lost에서 -1처리하여 삭제하고 reserve에서 -100 처리 해줍니다.

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n - lost.size();
    if (lost.size() == 0)
        return answer;
    sort(reserve.begin(), reserve.end());
    sort(lost.begin(), lost.end());
    /* 
        가져왔지만 도난당한 학생 처리
        lost 에서 삭제 = -1
        reserve 에서 삭제 = -100
    */ 
    for (int i = 0; i<lost.size(); i++) {
        for (int j=0; j<reserve.size(); j++) {
            if (lost[i] == reserve[j]) {
                answer++;
                lost[i] = -1;
                reserve[j] = -100;
                break;
            }            
        }
    }
    /*
        이미 처리한 애가 아니라면 작은 애한테 먼저 빌리기
        작은 애가 없다면 큰 애한테 빌리기
    */ 
    for (int i = 0; i < lost.size(); i++) {
        int curr_lost = lost[i];
        for (int j = 0; j < reserve.size(); j++) {
            int curr_reserve = reserve[j];
            if (curr_lost != -1 && curr_lost - curr_reserve == 1) {
                answer++;
                reserve[j] = -100;
                break;
            }
            if (curr_lost != -1 && curr_lost - curr_reserve == -1) {
                answer++;
                reserve[j] = -100;
                break;
            }
        }
    }
    return answer;
}