[PS/그리디/프로그래머스] 체육복

---

문제 설명

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

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

---

 

1차 시도

새벽 6시에 푸는 그리디 알고리즘 문제.
c++에서 벡터를 써본적이 없어 관련 api를 검색하면서 풀었다.
생각없이 짜본 첫 코드!

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

    for(int i = 0; i<lost.size();i++){
        for(int j = 0; j<reserve.size();j++){
            if(lost[i]==reserve[j]){
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);
                break;
            }
        }
    }
    for(int i = 0; i<lost.size(); i++){
        for(int j=0; j<reserve.size();j++){
            if((lost[i]+1==reserve[j])||(lost[i]-1==reserve[j])){
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);
            }
        }
    }

    return n-lost.size();
}

지금보니까 많이 조잡하넹 헤ㅔㅎ
먼저 여벌이 있었지만 도둑맞은 바보같은 학생을 뺐다.
그리고 잃어버린 학생을 차례로 순회하면서 잃어버린 학생의 앞이나 뒤 번호가 여벌옷을 가지고 있다면 각자 배열에서 삭제!
이 코드로 테스트케이스는 통과했지만 채점에선 반쪽짜리 답안이었다.
밍...무엇이 문제일까...
벡터에서 erase를 쓰면 인덱스가 중구난방으로 되는 문제도 있다고 하니 그 문제도 있으려나? 근데 전부 순회하는데 그게 문제가 되려나,,,
일단 반복문을 저렇게 쓰는건 시간복잡도면에서 낭비인것 같아서 처음부터 다시 시작하기로 했다.

2차 시도

먼저 벡터를 하나 만들고, 모든 학생이 옷 1벌을 기본으로 가지고 있다고 하자.
그리고 도둑맞은 학생들을 -1씩 하면 그분들은 0벌.
여벌을 가지고 있는 학생들을 +1씩 하면 여벌있는 분들은 2벌, 여벌 있었는데 도둑맞은 분들은 다시 1벌.
그리고 첫 학생부터 순회하면서 이 학생이 0벌이면 앞번호 먼저 확인해서 여벌있으면 가져오고, 아니면 뒷번호 확인해서 가져오고.
null참조는 방지해야하니까 조건 달아주면 괜찮을것 같았다.
1차시도와 비슷한 느낌지만, 인덱스를 직접 주무르는 느낌에서 조금 다른..?

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

good.

뭐가 다른건지 모르겠지만 아마 erase를 쓰는 과정에서 무언가 있었겠지.
풀고 다른분의 풀이를 보는데, 음 정말 깔끔한 코드가 있었다.

#include <string>
#include <vector>

using namespace std;
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;
}

저게 아마 확장for문이었던것 같은데,, 검색해보니까 for문에 auto키워드 사용해서 돌리기도하고 그러더라.
이분 코드는 null참조 걱정할 일도 없어보이구,, 고정크기배열이니까 실행속도도 괜찮을것같구,,,
부족한 나는 공부 열심히 해야겠다 헤헤,,,