[탐욕법] 체육복

|| 문제설명 ||

1. 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했다.
2. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 한다.
3. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다.
4. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 한다.
5. 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성하라.

• n : 전체 학생의 수
• lost : 체육복을 도난당한 학생들의 번호가 담긴 배열
• reserve : 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열

_ 전체 학생의 수 : 2명 이상 30명 이하
_ 체육복을 도난당한 학생의 수 : 1명 이상 n명 이하, 중복X
_ 여벌의 체육복을 가져온 학생의 수 : 1명 이상 n명 이하, 중복X
_ 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
_ 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 
  이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 
  남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

---

|| 문제해결방법 ||

체육복이 없는 번호의 앞, 뒤만이 체육복을 빌려줄 수 있고, 여벌을 가진 사람도 도난을 당할 수 있다.

...

1. lost 기준: O(n^2)

자신의 체육복을 가지고 있는 사람 : answer = n - lost.size()

미리 5번째 제한을 거르기 위해 lost와 reserve에 공통 사항들을 제외함

for문(i) → lost : 0 ~ lost.size()

for문(j) → reserve : 0 ~ reserve.size()

lost[i]의 -1 ~ +1까지의 번호를 reserve[j] 에서 찾고 찾으면 answer++; reserve[j] = 0; break; 실패하면 다음으로 넘어감.

2. 전체학생 기준: O(n)

---

|| 코드 ||

[2020.09.02] 성공

- lost 기준

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n - lost.size();
    
    // lost[i] == reserve[j] 은 사전에 제외
    for(int i=0; i<lost.size(); i++) {
        for(int j=0; j<reserve.size(); j++) {
            if(lost[i] == reserve[j]) {
                answer++;			// 보통의 아이로 포함.
                lost[i] = reserve[j] = 0;	// 나중에 for문을 돌릴때 제외하기 위함.
                break;	
            }
        }
    }
    
    for(int i=0; i<lost.size(); i++) {
        if(lost[i]) {
            for(int j=0; j<reserve.size(); j++) {
                if(reserve[j]) {
                    int tmp = lost[i]-reserve[j];
                    if(-1 == tmp || tmp == 1) {	// 앞, 뒤 사람인지 판별
                        answer++;	
                        reserve[j] = 0;
                        break;
                    }
                }
            }
        }
    }
    return answer;
}

---

[2021.02.17]

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        int[] people = new int[n];
        
        Arrays.fill(people, 1);
        for(int i = 0; i < n; i++) {
        	if(i < lost.length) people[lost[i]-1]--;
        	if(i < reserve.length) people[reserve[i]-1]++;
        }
        for(int i = 0; i < n; i++) {
        	if(people[i] > 0) continue;
        	
        	if(people[i-1] == 2) people[i-1]--;
        	else if(people[i+1] == 2) people[i+1]--;
        	else answer--;
        }        
        return answer;
    }
}

엄청난 런타임 에러....

---

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        int[] people = new int[n+1];
        
        for(int i = 0; i < reserve.length; i++) {
            people[reserve[i]]++;
        }
        for(int i = 0; i < lost.length; i++) {
            if(people[lost[i]] == 1) {
                people[lost[i]]--; 
                continue;
            }
            if(people[lost[i]-1] == 1) people[lost[i]-1]--;
        	else if(people[lost[i]+1] == 1) people[lost[i]+1]--;
        	else answer--;
        }
        return answer;
    }
}

여분의 옷을 가진 사람이 자신의 체육복을 잃어버린 경우

---

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;
    vector<int> people(n+1);
        
        for(int i = 0; i < reserve.size(); i++) {
            people[reserve[i]]++;
        }
        for(int i = 0; i < lost.size(); i++) {
            if(people[lost[i]] == 1) people[lost[i]]--; 
            else if(people[lost[i]-1] == 1) people[lost[i]-1]--;
        	else if(people[lost[i]+1] == 1 && lost[i]+1 != lost[i+1]) 
                people[lost[i]+1]--;
        	else answer--;
        }
        return answer;
}