[C++] 체육복

링크

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

프로그래머스

문제

입출력 예제

코드

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

using namespace std;

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

    answer = n - lost.size();

    // 여벌 체육복을 들고온 학생 체크
    for(int i = 0; i < reserve.size(); i++)
    {
        int targetPos = reserve[i] - 1;
        canLend[targetPos] = true;
    }
    
    // 도난당한 학생이 여별 체육복이 있다면 해당 체육복 사용
    // 다른 학생에게는 못 빌려줌
    for(int i = 0; i < lost.size(); i++)
    {
        int targetPos = lost[i] - 1;

        if(canLend[targetPos])
        {
            canLend[targetPos] = false;
            completed[targetPos] = true;
            answer++;
            continue;
        }
    }
    

    sort(lost.begin(),lost.end());    
    // 도난당한 학생에게 체육복을 빌려줄 수 있는지
    for(int i = 0; i < lost.size(); i++)
    {
        int targetPos = lost[i] - 1;
        
        if(completed[targetPos]) continue;

        if(canLend[targetPos - 1] && targetPos > 0)
        {
            canLend[targetPos - 1] = false;
            answer++;

        }
        else if(canLend[targetPos + 1] && targetPos < n - 1)
        {
            canLend[targetPos + 1] = false;
            answer++;
        }
    }
        
    return answer;
}

풀이

체육복을 잃어버린 사람 목록은 lost, 여분을 가지고 있는 사람 목록은 reserve 입니다.

 

lost와 reserve 둘 다 속해있을 수 있습니다. 둘 다 속해있을 경우 자신의 여분을 사용하기 때문에 다른사람에게
체육복을 건네줄 수 없습니다.

 

빌려줄 수 있는지 여부를 저장하는 canLend 라는 이름의 bool형 벡터와
물건을 잃어버렸지만 자신의 여분을 사용했음을 판단하기 위한 complete라는 이름의 bool형 벡터를 선언합니다.

 

reserve 벡터를 탐색해서 해당 벡터 목록에 존재하는 사람은 canLend를 true로 바꿔줍니다.

lost 벡터에 속해있는 사람 중 canLend가 true인 사람은 여분을 들고온 사람을 뜻하니

자신의 여분 체육복을 사용 했으므로 canLend를 false로 다시 바꿔주고,

lost 목록에는 있지만 자신의 체육복을 사용했음을 판단하기 위해 complete를 true로 바꿔줍니다.

 

이후 lost 목록을 반복문으로 탐색하여 complete가 true라면 continue로 넘기고,
자신의 인덱스의 앞 뒤 인덱스가 canLend가 true라면 체육복을 빌립니다.