체육복 - 프로그래머스, c++

 

 

- 문제 풀이

"탐욕법(Greedy)"를 이용하는 문제였다.

 

문제를 풀기 전 탐욕법, 그리디 알고리즘에 대해 공부했다.

https://sectumsempra.tistory.com/88

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

그리디 알고리즘의 특징은 단순하고 빠르다는 것이다.

또 다른 특징은 이후의 경우는 생각하지 않고 현재의 상황에서 가장 최적의 값을 따라 간다는 것이다. 가장 최적화된 값보다 덜 효율적인 답을 내놓게 될 수도 있다.

따라서 그리디 알고리즘을 사용하려면 그리디 알고리즘을 사용해 문제를 해결하는 것이 가장 효율적인 지 그 근거가 필요하다.

 

그리디 알고리즘
1. 일반적으로 최대한 적은, 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 최대/최소의 경우의 수를 구할것을 요구하는 문제들이다.
2. 그리디를 사용할 수 있는 조건이 주어진다. (주로 문제를 읽고 조건을 찾아야한다.)
3.정렬을 한 뒤 그것을 이용해 푸는 문제가 많다. (위 동전문제의 경우에도 동전을 내림차순으로 정렬한 뒤 하나 하나 사용해 나가야 할 것이다.)

 

 

- 코드

처음 제출한 코드는 다음과 같다.

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    //필요한 변수 선언
    int answer = 0;
    vector<int> cloth_num(n, 1); //n개의 원소를 1로 초기화하여 벡터 선언
    
    //각 학생이 가진 체육복 수 update
    for(int i=0; i<lost.size(); i++) {
        cloth_num[lost[i]-1] -= 1;
    }
    for(int i=0; i<reserve.size(); i++) {
        cloth_num[reserve[i]-1] += 1;
    }
    
    //cloth_num 벡터를 탐색하며 체육복 빌려주기
    if(cloth_num[0]<=0 && cloth_num[1]>=2) {
        cloth_num[0] = 1;
        cloth_num[1] -= 1;
    }
    for(int i=1; i<n-1; i++) {
        if(cloth_num[i]<=0){
            if(cloth_num[i-1]>=2) {
                cloth_num[i] = 1;
                cloth_num[i-1] -= 1;
            }
            else {
                if(cloth_num[i+1]>=2) {
                    cloth_num[i] = 1;
                    cloth_num[i+1] -= 1;
                }
            }
        }
    }
    
    //cloth_num 벡터를 통해 수업 들을 수 있는 학생 수 계산
    for(int i=0; i<n; i++) {
        if(cloth_num[i]>=1)
            answer++;
    }    
    
    return answer;
}

하지만 위와 같은 결과가 나왔다.

 

탐색하며 체육복을 빌려주는 과정에서

vector의 가장 마지막에 있는 학생(n번 학생)은 무조건 그 앞에 있는 학생(n-1번 학생)에게 빌려야하므로

1번 학생과 같이 따로 미리 고려해주어야 했다.

최종으로 제출한 코드는 다음과 같다.

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    //필요한 변수 선언
    int answer = 0;
    vector<int> cloth_num(n, 1); //n개의 원소를 1로 초기화하여 벡터 선언
    
    //각 학생이 가진 체육복 수 update
    for(int i=0; i<lost.size(); i++) {
        cloth_num[lost[i]-1] -= 1;
    }
    for(int i=0; i<reserve.size(); i++) {
        cloth_num[reserve[i]-1] += 1;
    }
    
    //cloth_num 벡터를 탐색하며 체육복 빌려주기
    if(cloth_num[0]<=0 && cloth_num[1]>=2) {
        cloth_num[0] = 1;
        cloth_num[1] -= 1;
    }
    if(cloth_num[n-1]<=0 && cloth_num[n-2]>=2) {
        cloth_num[n-1] = 1;
        cloth_num[n-2] -= 1;
    }    
    for(int i=1; i<n-1; i++) {
        if(cloth_num[i]<=0){
            if(cloth_num[i-1]>=2) {
                cloth_num[i] = 1;
                cloth_num[i-1] -= 1;
            }
            else {
                if(cloth_num[i+1]>=2) {
                    cloth_num[i] = 1;
                    cloth_num[i+1] -= 1;
                }
            }
        }
    }
    
    //cloth_num 벡터를 통해 수업 들을 수 있는 학생 수 계산
    for(int i=0; i<n; i++) {
        if(cloth_num[i]>=1)
            answer++;
    }    
    
    return answer;
}