[programmers/c++] 체육복

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> student(n+1, 1);

    for (int s : lost)
        student[s] -= 1;
    for (int s : reserve)
        student[s] += 1;

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

    for (int i=1;i<=n;i++)
        if (student[i] > 0) answer++;

    return answer;
}

 

의아한 점

왜 앞 사람 먼저 빌려주는 게 맞는지?

if (student[i+1] == 1) 의 경우를 먼저 작성해주면 테스트케이스 17~20번에서 실패한다.

 

 

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

using namespace std;

vector<int> lost_b, surplus;
vector<bool> losts, used;
int k, bestAnswer;


bool isExists(vector<int> v, int t) {
    if (find(v.begin(), v.end(), t) != v.end())
        return true;
    return false;
}

bool isAllLostsStudentBrought() {
    for (int l : lost_b)
        if (!used[l])
            return false;
    return true;
}

bool isAllReservedStudentDonated() {
    for (int s : surplus) {
        if (!used[s])
            return false;
    }
    return true;
}

void run(int answer) {
    if (isAllReservedStudentDonated() ||
        isAllLostsStudentBrought()) {
        if (answer>bestAnswer)
            bestAnswer = answer;
        return;
    }

    for (int s : surplus) {
        if (used[s]) continue;
        
        used[s] = true;
        
        if (s<k && losts[s+1] && !used[s+1]) {
            used[s+1] = true;
            answer++;
            
            run(answer);
            
            used[s+1] = false;
            answer--;
        }
        
        else if (s>1 && losts[s-1] && !used[s-1]) {
            used[s-1] = true;
            answer++;
            
            run(answer);
            
            used[s-1] = false;
            answer--;
        }

        else {
            run(answer);
        }

        used[s] = false;
    }
}

int solution(int n, vector<int> lost, vector<int> reserve) {
    k=n;

    for (int i=0;i<=k;i++) {
        used.push_back(false);
        losts.push_back(false);
    }
    
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
    
    int lostCount=0;
    for (int i : lost) {
        losts[i] = true;
        lostCount++;
    }
    
    for (int s : reserve) {
        if (isExists(lost, s)) {
            losts[s] = false;
            lostCount--;
        }
        else
            surplus.push_back(s);
    }
    
    for (int i=1;i<=k;i++)
        if (losts[i])
            lost_b.push_back(i);

    run(n-lostCount);

    int answer = bestAnswer;
    return answer;
}

 

부끄럽지만 겨우 통과한 나의 첫 코드

위에서 하나만 안 해도 테스트케이스 7번은 시간초과로 실패된다.

굳이 재귀를 사용하지 않아도 되는 문제였다