[프로그래머스]탐욕법 - 체육복

문제

 

풀이

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> students(n, 1);
    
    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<n; i++){
        if(students[i] == 0){
            if(i>0 && students[i-1] > 1){answer++; continue;}
            if(i<n-1 && students[i+1] > 1) {students[i+1]--;answer++; continue;}
        }
        else answer++;
    }
    
    return answer;
}

그리디 알고리즘(탐욕 알고리즘)

-최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 

 

처음에는 이중 반복문을 사용해 reverse, lost벡터를 각각 탐색하려 했으나,

각각의 학생이 가지고 있는 체육복의 수를 나타내는 벡터 배열을 만드는 것이 더 효율적일 것이라는 생각이 들어 students벡터 배열을 만들었고, 한 번의 반복문으로 해결하게 되었다.

 

 

 

풀이 2

#include <string>
#include <vector>

using namespace std;

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

반복문을 수정해주었다.

 

 

 

---

다른 사람 풀이

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

 

---

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전