프로그래머스 탐욕법 알고리즘, 체육복 문제풀이

 

오늘은 탐욕법 알고리즘문제, 체육복을 풀어보겠습니다. 프로그래머스 알고리즘 문제 사이트에 있는 1단계문제 중 하나로, 왕초보분들은 풀이에 약간 어려움이 있을 수 있는 문제인것 같습니다. 이 문제는 탐욕법 문제라고 하는데요.

탐욕법(Greedy Algorithm)

● 문제를 작은 단위로 쪼개고 반복적으로 진행하며 접근하는 방식은 완전탐색 등과 유사

● But, 탐용법은 각 단계에서 그 시점에 가장 좋아 보이는 선택을 한다.

- 앞으로의 선택 혹은 최종 결과는 고려하지 않는다.

- 탐욕법의 해가 반드시 최적의 해라는 보장은 없다.

와 같은 특징을 갖고 있습니다. 탐욕법은 당장 앞에 보이는 가장 좋아보이는 선택을 하는 특징이 있는데, 이는 반드시 최적의 해임을 보장할 수는 없지만, 간단한 알고리즘문제의 경우 얼추 괜찮은 결과를 보여주기도 하는 풀이방법입니다. 

그렇다면 체육복 알고리즘의 문제를 보겠습니다.

 

♣︎ 체육복 알고리즘 문제 설명

점심시간에 도둑이 들어 일부학생이 체육복을 도난당한 상태입니다. 여벌 체육복이 있는 사람은 있지만, 체육복은 양옆 번호 학생에게만 빌려줄 수 있습니다. 단, 학생복 여벌이 없는 학생은 여분이 아닌 자기자신의 체육복을 양옆 학생에게 빌려줄 수 없습니다.

자기자신은 입어야하니 그렇습니다.

전체 학생의 수는 2~30명이며, 중복된 번호는 없습니다. 여기서 학생의 번호란, 각 학생의 인덱스로 생각하시면 됩니다. 가령 5명의 학생이 있다면, 1~5의 학생번호를 가집니다. 

 

 

입출력 예시입니다. n(학생의 수), lost(잃어버린학생의 번호), reserve(여분 체육복을 가진 학생의 번호) 세가지 인자를 받아 결과값을 호출합니다. 체육복 여분을 가진 학생들은 양옆의 학생들에게 체육복을 빌려줄지, 말지를 판단해야하는 상황입니다. 그럽 한번 문제를 풀어보겠습니다. 

 

♣︎ 체육복 알고리즘 문제 풀이

#include <iostream>
#include <vector>
using namespace std;
int solution(int n, vector lost, vector reserve) {
    int answer = 0;
    
    // 0] 학생의 체육복 정보를 저장할 벡터를 초기화한다.(초기 값 1로 설정)
    vector student(n,1);
    
    // 1] 학생 별 체육복의 갯수를 셋팅한다.
    for(int i : lost){
        
        /////::: Code ::://///  // 잃어버린 학생의 체육복-- (0이 됨)
    }
    for(int i : reserve){
        
        /////::: Code ::://///  // 여분이 있는 학생의 체육복++ (2가 됨)
    }
    
    // 2] 좌측학생 > 우측학생을 우선으로 체육복을 빌려줄지 판단한다.
    for(int i=0; i<student.size(); i++){
        if(i!=0 && student[i-1]==0){ // 맨 앞사람이 아닌 사람 중 앞사람이 옷이 부족하다면
            if(student[i] == 2){     // 여분이 있을경우 좌측사람++ 본인--
                
                /////::: Code ::://///
                continue;
            }
        }
        if(i!=student.size()-1 && student[i+1]==0){ // 맨끝사람이 아니고, 뒷사람이 옷이없으면,
            if(student[i]==2){    // 여분이 있을경우 우측사람++ 본인--
                
                /////::: Code ::://///
            }
        }
    }
    
    // 3] 1개이상 체육복을 소지중인 학생의 수를 답에 대입한다.
    for(int i=0; i<student.size(); i++){
        if(student[i]>0){
            answer++;
        }
    }
    
    return answer;
}

 

• 학생 별 체육복 갯수를 셋팅합니다. 체육복이 없는 학생은 -1(0개가 됨), 여분이 있는 학생은 +1(2개가 됨) 처리해줍니다. 
• 맨 앞 번호를 제외한 학생들은 자신이 여분이 있을때 앞번호사람이 체육복이 없으면 체육복을 빌려줍니다. 맨 뒷 번호를 제외한 학생들은 자신이 여분이 있을때 뒷번호사람이 체육복이 없으면 체육복을 빌려줍니다. 
• 최종적으로 1벌이상의 체육복이 있는 학생들의 수를 출력합니다. 

인덱스가 0~N-1로 다뤄진다는 것만 주의하여 구현하시면 문제없이 푸실 수 있습니다.