문제

문제 설명

제한사항 입출력 예

문제 해석

우선 체육복을 잃어버린 학생의 번호 -> lost
체육복 여분을 가진 학생의 번호 -> reserve
입력으로 n명의 학생을 받는다.
제한사항으로 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호가 없다고 한다. 그리고 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호가 없다. 여벌 체육복을 가지고 있는 학생만 다른 체육복을 빌려줄 수 있다.
또 lost와 reserve의 번호가 서로 인접한 학생의 번호 일시에만 빌려줄 수 있다.
예를 들어서 2번이 여분을 보유할 경우 lost의 1번과 3번에게만 빌려줄 수 있다고한다.

문제 해결 전략

순차적으로 탐색해서 reserve의 값을 우선 탐색하여 lost에 reserve번호에 인접한 경우만 빌려줄수 있으므로 패스하고 그외에는 n의 값에 n--를 하면서 return값을 줄여나가는 방식을 적용시켜봐야겠다.

코드1

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n; int r = 0;
    for(int i = 0;i < lost.size();i++){
        if(lost[i] == reserve[r]-1 || lost[i] == reserve[r]+1) {r++; continue;}
    answer--;
    if(reserve.size() == r) break;
    }
    return answer;
}

우선 틀렸다.. 정확성 33.3%밖에 못가졌다. 우선 다른 테스트 케이스를 돌려보니 잘못됐다는 것을 깨닳았다..

코드2

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n; int i = reserve.size()-1;
    int item = 0;
    while(1){
        if(lost.size() == 0) break;
        item = lost.back(); lost.pop_back();
        if(item+1 == reserve[i] || item-1 == reserve[i]) {i--; continue;}
        answer--;
    }
    return answer;
}

정확도가 더 낮은 16.7이 나왔다. 처음부터 다시 접근해야겠다..

코드3

#include <vector>
#include <string>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve)
{
	int answer = 0;
	vector<int> s(n, 1);
	for (auto a : reserve)
		s[a - 1]++;
	for (auto a : lost)
		s[a - 1]--;

	for (int i = 0; i < s.size(); i++)
	{
		if (i != 0 && s[i] == 0)
		{
			if (s[i - 1] == 2)
			{
				s[i]++;
				s[i - 1]--;
				continue;
			}
		}
		if (i != s.size() - 1 && s[i] == 0)
		{
			if (s[i + 1] == 2)
			{
				s[i]++;
				s[i + 1]--;
			}
		}
	}
	for (auto a : s)
		a > 0 ? answer++ : 0;

	return answer;
}

하 멀고도 험했다..