프로그래머스 - 체육복 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    vector<int> arr(n+1,0);
    
    for(int i=0;i<lost.size();i++)arr[lost[i]]=-1;
    for(int i=0;i<reserve.size();i++){
        if(arr[reserve[i]]==-1)
            arr[reserve[i]]=0; // 여벌을 가져왔지만 도난당함
        else
            arr[reserve[i]]=1;
    }
    
    for(int i=1;i<n+1;i++)
    {
        if(arr[i]==-1)
        {
            if(i-1>0&&arr[i-1]==1)
            {
                arr[i]=0;
                arr[i-1]=0;
            }
            else if(i+1<n+1&&arr[i+1]==1)
            {
                arr[i]=0;arr[i+1]=0;
            }        
        }
    }
    for(int i=1;i<n+1;i++)
        if(arr[i]!=-1)
            answer++;
    return answer;
}

 

이 문제는 체육복을 도난당한 사람의 번호리스트와 여벌옷을 가져온 사람의 번호리스트가 주어진다.

여벌옷을 최대한 많이 빌려서 최대한 많은사람이 체육복을 입을 수 있을 때, 몇명이 가능한가를 리턴하는 문제이다.

 이 때,  n번이 여벌이 있다면 n-1, n+1번에게만 빌려줄 수 있다. 

 

이 문제가 그리디로 구분이 돼있어서 쉽게 접근할 수 있었다. 

greedy 란 각각의 현재상황에서 최선의 경우를 찾는 방법을 말한다. 그렇게 계속 최선의 방법을 찾아가다보면 

마지막 결과도 최선이 된다는 것이다. 

 

따라서 n번이 만약 체육복이 없다면 n-1번에게 빌리는 것이 최선이며, 그 차선책이 n+1번에게 빌리는 것이다. 

왜냐면 n+1번에게 빌리면 n-1번이 여벌옷을 가지고 있을 때, 1개가 낭비되기 때문이다. 

 

lost와 reserve를 하나의 리스트로 표현해서 처리해야 편하겠다는 생각을 했다.

 

vector<int> arr(n+1,0);
    
    for(int i=0;i<lost.size();i++)arr[lost[i]]=-1;
    for(int i=0;i<reserve.size();i++){
        if(arr[reserve[i]]==-1)
            arr[reserve[i]]=0; // 여벌을 가져왔지만 도난당함
        else
            arr[reserve[i]]=1;
    }

 

arr에 번호와 체육복의 유무를 나타낸다.

-1 = 옷 없음, 0 = 자기것만 있음, 1 = 여벌이 있음

if문은 여벌옷을 가져왔지만 도난 당한 경우때문이다.

 

for(int i=1;i<n+1;i++)
    {
        if(arr[i]==-1)
        {
            if(i-1>0&&arr[i-1]==1)
            {
                arr[i]=0;
                arr[i-1]=0;
            }
            else if(i+1<n+1&&arr[i+1]==1)
            {
                arr[i]=0;arr[i+1]=0;
            }        
        }
    }

arr배열을 for문으로 돌면서 옷이 없을 때, n-1번에게 물어보고 그 다음 n+1번에게 물어본다. 

빌리면 상태를 0으로 변경한다.

 

for(int i=1;i<n+1;i++)
        if(arr[i]!=-1)
            answer++;

마지막으로 -1이 아니라면 체육복이 있는상태이므로 계산한다.