[C++] 프로그래머스 - 체육복 (그리디)

그리디의 대표 문제 중 하나인 체육복이다.

프로그래머스

 

 

 

문제 요약

전체 학생 n(2~30)명 중 체육복을 도난당한 학생들(lost)이 있다. 체육복이 없는 학생의 앞뒤 번호 중 여벌을 가져온 학생(reserve)이 있으면 체육복을 빌린다. 도난은 1개씩만 당하며, 여벌을 가져온 학생도 도난 당해서 여벌이 없어졌을 수 있다. 이렇게 빌려서 수업을 들을 수 있는 학생 수의 최대값을 반환하면 된다.

내 풀이

학생수만큼 각 번호에 1을 담은 배열을 두고, 도난을 당했으면 1을 빼고 여벌을 가져왔으면 1을 더해준다.
lost를 정렬한 다음, 도난당한 학생의 앞번호가 여벌을 가져왔으면 빌리고, 뒷번호만 가져왔으면 뒷번호에게 빌린다.
다 빌린 다음 배열에 0이 아닌 값(1,2)이 들어있는 학생수만큼 세서 반환했다.

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

using namespace std;

int stu[31];

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer=0;
    for(int i=1; i<=n; i++) {
        stu[i]++;
    }
    sort(lost.begin(), lost.end());
    for(int i=0; i<lost.size(); i++) {
        if(lost[i]) stu[lost[i]]--;
    }
    for(int i=0; i<reserve.size(); i++) {
        if(reserve[i]) stu[reserve[i]]++;
    }
    for(int i=0; i<lost.size(); i++) {
        if(!stu[lost[i]]) {
            if(stu[lost[i]-1]==2) {
                stu[lost[i]-1]--, stu[lost[i]]++;
            } else if(stu[lost[i]+1]==2) {
                stu[lost[i]+1]--, stu[lost[i]]++;
            }
        }
    }

    for(int i=1; i<=n; i++) {
        if(stu[i]) answer++;
    }

    return answer;
}

 

다른 사람 풀이

푸는 방식은 비슷한데, 학생수만큼 배열에 1을 넣는 과정 없이 lost 번호의 배열에 -1, reserve 번호의 배열에 1을 넣었다.
그리고 정렬 후 lost 배열을 검사했던 나와 달리, 정렬하는 과정 없이 그냥 모든 학생을 검사해 체육복을 빌리는 과정을 수행했다.

#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;
}