[Algorithm] Programmers :: 체육복

https://programmers.co.kr/learn/courses/30/lessons/42862?language=cpp 

코딩테스트 연습 - 체육복

int solution(int n, vector<int> lost, vector<int> reserve) {
 
    int answer = 0;
    
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());
 
    for (int i = 1; i <= n; i++) // 전처리과정. 도난당한사람과 여벌옷있는 사람은 검사에서 제외. 본인꺼 쓰니까.
    {
        auto t1 = find(lost.begin(), lost.end(), i) - lost.begin();
        auto t2 = find(reserve.begin(), reserve.end(), i) - reserve.begin();
 
        if (t1 != lost.size() && t2 != reserve.size()) // 같은값이 둘 다에 있으면,
        {
            lost.erase(lost.begin() + t1);
            reserve.erase(reserve.begin() + t2);
        }
    }
 
    for (int i = 0; i < lost.size(); i++)
    {
        int stand = lost[i];
 
        for (int j = 0; j < reserve.size(); j++)
        {
            if (stand >= reserve[j] - 1 && stand <= reserve[j] + 1) // 빌릴 수 있으면,
            {
                // rserve[i] 삭제.
                lost.erase(lost.begin() + i);
                i--;
                reserve.erase(reserve.begin() + j);
                break;
            }
        }
    }
 
    return n - lost.size();
}

먼저 sort를 해준건, 문제에서 예시에는 오름차순으로 되어있는데 실제로는 아니라고 한다. 

sort 해주기전에는 13,18번을 틀렸지만 sort를 해주니까 둘 다 통과가 뜨면서 문제를 해결했다.

다만, n의 크기나 lost,reserve의 사이즈가 클수록 효율적이지는 않은 코드다.

처음 전처리과정에서 lost랑 reserve에 같은 값이 있으면 삭제하게 했는데(여벌=도난당한 사람이 같은사람은 제외), 이런 경우는 n의 크기에 영향을 받는다. 일단 시행횟수는 n이다. 그리고 이 n번만큼 find함수를 실행하는데 find함수의 시간복잡도도 f(n)이다. 실제 밑에 답을 구하는 코드도 마찬가지고, 매개변수 벡터의 사이즈가 클 경우 아마 효율성에서 컷트가 나지 않았을까 한다.

 위처럼 짜지말고, 아래처럼 짜는게 좋다.

 

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