[프로그래머스] 체육복 C++

programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

 

 처음엔 map으로 문제를 풀었다. 백터로 할 수도 있겠다 싶었음. 백터가 가지고 있는 값을 흔히 i로 가리킨다. 이 i로 학생을 가리키고 있어서 백터로 풀 수 있는 것 같다. 학생을 고유 이름을 나타냈다면 백터로 풀기 힘들었을까? 그럼 문제의 조건이 완전히 바뀌긴 한다. map을 사용하는 문제는 백터 2개를 사용하면 풀수 있지만 번거롭다.

 

문제를 제대로 읽지 않아서 reserve에 속한 학생이 lost에도 속할 수 있다는 조건을 파악하지 못했다. 문제를 읽고 이해하는데 더 신경써야한다.

 

체육복을 뒷 사람에게 먼저 빌려주는 경우, 체육복을 앞 사람에게 먼저 빌려주는 경우가 각각 다른 값이 나오면 최댓값을 반환하려고 했다. 예를 들어 2 4가 체육복이 없는데 3 5가 여유분을 가지고 있다고 하면3이 뒷 사람에게 먼저 빌려주는 경우 5는 아무에게도 빌려주지 않게 되어 답이 달라진다. 하지만 이러한 경우를 고려하지 않아도 되더라. 다른 풀이를 보니 이 경우를 생각하지 않아도 답은 잘나왔다. 뒷 사람에게 먼저 빌려주는 경우와 앞 사람에게 먼저 빌려주는 경우를 구분 할 필요는 없으며, 앞사람에게 먼저 빌려주는 경우만 고려해도 문제를 푸는데 이상이 없다....

    void work(vector<int>& v, vector<int>& reserve, bool isOn){
        if(isOn){
            for(int i:reserve){
                if(v.at(i-1)==-1){ v.at(i-1)=1; }
                else if(v.at(i+1)==-1){ v.at(i+1)=1;}
            }
        } else {
            for(int i:reserve){
                if(v.at(i+1)==-1){ v.at(i+1)=1;}
                else if(v.at(i-1)==-1){ v.at(i-1)=1; }
            }
        }
    }
    

    int utility(int n, vector<int> &lost, vector<int> &reserve, bool isOn){
        vector<int> v(30,0);
        for(int i=0; i<30; ++i) v[i]=0;
        for(int i: lost) v[i]=-1; 

        work(v,reserve,isOn);
        int count=0;
        for(int i:v) if(i==1){ count++; }
        return n-lost.size()+count;
    }

    int solution(int n, vector<int> lost, vector<int> reserve) {
        sort(lost.begin(),lost.end());
        sort(reserve.begin(),reserve.end());
        int a=0, b=0;
        while( a< lost.size() && b<reserve.size() ){
            if( lost.at(a) < reserve.at(b)){ a++; } 
            else if( lost.at(a) > reserve.at(b) ){ b++; }
            else {
                lost.erase(lost.begin()+a); a=0;
                reserve.erase(reserve.begin()+b); b=0;
            }
        }
        int frontFirst = utility(n,lost,reserve,true);
        int rearFirst = utility(n,lost,reserve,false);
        return frontFirst>rearFirst? frontFirst:rearFirst;
    }

다른 사람 풀이에서 찾은 간단한 풀이ㅠ.ㅠ이렇게 간단히 풀다니.

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