[프로그래머스/level1 / c++] 체육복

 

문제 :

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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

 

코드 :

#include <string>
#include <vector>

using namespace std;

//reserve의 값과 lost의 왼쪽,오른쪽 같은지 확인
bool check(int num,int index,vector<int> &lost,vector<int> &reserve){
    for(int i=0;i<reserve.size();i++){
        if(num==reserve[i]){
            lost.erase(lost.begin()+index); //lost를 삭제하고
            lost.insert(lost.begin()+index,0); //삭제한 곳에서 0 집어넣기
            reserve.erase(reserve.begin()+i); //reserve삭제
            return true;
        }
    }
    return false;
}
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = n;
    
    //reserve와 lost 같은값 삭제해주기
    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);
                i--;
                j--;
            }
        }
    }
    
    //lost의 앞번호와 뒷번호 확인하기
    for(int a=0;a<lost.size();a++){
        if(lost[a]-1==0 || !check(lost[a]-1,a,lost,reserve)){ //앞번호 확인
            if(lost[a]+1==n+1 || !check(lost[a]+1,a,lost,reserve)) //뒷번호 확인
                answer--; //둘다 없으면 학생 수 감소
        }
    }
    return answer;
}

 

다시 한번 짚고 넘어가기 : 

vector를 매개변수로 보낼 때 호출한 함수안에서 vector값을 변경하고자 할때 call by value가 아닌 call by reference를 해주어야한다. 왜냐하면 스택에 서로 따로 존재하기 때문에 둘 중 뭘 수정해도 서로 영향이 가지 않는다. &를 사용하지 않으면 메모리를 추가로 사용하지 않고 복사하는데 걸리는 오버헤드가 더 적다. ex( line 7처럼 vector<int> &lost )

 

vector의 erase함수를 사용할 때 주의할 점은 배열의 뒷요소들이 자동으로 한칸씩 당겨지기 때문에 vector를 순차적으로 탐색하여 원하는 인덱스에 erase를 사용할 땐 주의가 필요하다.

vector<int> vec;
for(int i=0;i<vec.size();){
	if(삭제 조건문)
    	vec.erase(vec.begin()+i);
    else
    	i++;
}

 

도움이 된 글 :

www.acmicpc.net/board/view/38804

글 읽기 - c++ string 과 vector 를 매개변수로 넘길때 질문입니다.

codechacha.com/ko/cpp-stl-vector/

C++ STL Vector 사용 방법