Programmers > 코딩테스트 연습 > 탐욕법 > 체육복

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42862/solution_groups?language=cpp

풀이

먼저 여분의 옷을 가지고 있는 친구와 잃어버린 친구를 쉽게 구분하기 위해 다음과같이 map을 

써서 저장해 놓았다.

    for(int i=0; i<lost.size(); i++) lost_student[lost[i]]++;
    for(int i=0; i<reserve.size(); i++) reserve_student[reserve[i]]++;

그 다음 1부터 n까지 반복문을 수행하면서 n번째 사람이 잃어버리지 않았다면 결과값에 1추가,

체육복을 잃어버렸다면 앞에 사람, 나 자신, 뒤에 사람한테 체육복이 있는지 확인하고

결과값에 1을 추가하는 과정을 반복하였다. (맨 처음과 맨 뒷사람은 별도로 조건문을 써 주었다.)

이렇게 하다보니 몇몇 테스트 케이스를 통과할 수 없었는데 이를 해결하기 위해

만약 2번이 옷을 잃어버린 상태에서 3번한테 여벌의 옷이 있을 때 

3번또한 옷을 잃어버렸다면 3번에게 옷을 빌릴 수 없다는 것을 조건문에 반영해야하며

옷을 잃어버렸을 때 제일 먼저 자신에게 여벌이 있는지 확인한다는 것을 조건문에 반영해야

모든 테스트케이스를 통과할 수 있었다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    map<int,int> lost_student;
    map<int,int> reserve_student;
    for(int i=0; i<lost.size(); i++) lost_student[lost[i]]++;
    for(int i=0; i<reserve.size(); i++) reserve_student[reserve[i]]++;

    int result = 0;

    for(int i=1; i<=n; i++)
    {
        if(lost_student[i] == 0) result++;
        else{
            if(i == 1){
                if(reserve_student[1] == 1){
                    reserve_student[1]--;
                    result++;
                }
                else if(reserve_student[2] == 1){
                    if(lost_student[2] == 0){
                    reserve_student[2]--;
                    result++;}
                }
            }
            else if(i == n){
                if(reserve_student[n] == 1){
                    reserve_student[n]--;
                    result++;
                }
                else if(reserve_student[n-1] == 1){
                    reserve_student[n-1]--;
                    result++;
                }
            }
            else{
            if(reserve_student[i] == 1){
                    reserve_student[i]--;
                    result++;
                }
                else if(reserve_student[i-1] == 1){
                    reserve_student[i-1]--;
                    result++;
                }
                else if(reserve_student[i+1] == 1){
                    if(lost_student[i+1] == 0){
                    reserve_student[i+1]--;
                    result++;}
                }
            }
        }
    }
    return result;
}