[프로그래머스/C++] ㅡ LV1 - 체육복

문제

programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

풀이

#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    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);
                break;
            }
        }
    }
     int answer = n-lost.size();
     for (int i=0; i<lost.size(); i++) {	// 빌려주기
        for (int j=0; j<reserve.size(); j++) {
            if (lost[i] == reserve[j]-1 || lost[i] == reserve[j]+1) {
                reserve.erase(reserve.begin()+j);
                answer++;
                break;
            }
        }
    }
    return answer;
}

개념

탐욕법에 해당하는 문제라고 한다.

사실 그리디 알고리즘을 아직 배우지 않아서, 생각나는대로 풀었다.

매 선택에서 지금 최적인 답을 선택하여 결과까지 도달하는 방법이라고 한다.

 

vector의 함수 중 erase를 이용했다.

erase()의 인자에는 해당 위치를 대입하면 된다.

벡터의 위치를 넣기 위해, begin 함수도 사용했다.

---

풀이

문제를 풀기위해 두가지 단계를 거친다.

 

① 도난당한 학생이 여벌의 체육복을 가진 경우, lost 배열과 reserve 배열에서 제외시킨다.

② 여벌의 체육복을 나눠준다.

 

답을 구하는 방식은 다음과 같다.

 

①을 거친 뒤, answer에 n - lost.size() 를 대입한다.

그리고 ②를 반복하며 체육복을 나눌 때마다 answer++ 를 하면 된다.

 

 

일단 lost 배열과 reserve 배열에서 같은 값을 빼주어야 한다.

하지만 배열에서 값을 제외하는 것은 그리 간단하지 않다.

for문을 통해 배열의 크기만큼 반복하고 있기 때문이다.

몇번 출력 연습을 한 결과, 반복문 내 배열 원소 제거는 아래 그림과 같은 원리를 가진다.

배열의 index는 이동하는데, for문에서는 i=0 다음 i=1을 반복한다.

따라서 1 -> 2 -> 3 이 아니라, 1 -> 3 의 과정을 거치게 된다.

이를 방지하기 위해 식에 i--를 넣었다.

j의 경우 < reserve.size()의 경우 >는 따로 --를 하지 않았는데 break 하기 때문이다.

 

이제 lost[ ]에 대해 reserve[ ] 값이 ±1인 경우에 한해 체육복을 나눠준다.

lost를 기준으로 반복하여, or 연산을 통해 reserve[] -1 을 reserve[] +1 보다 먼저 비교한다.

이 때마다 answer++ 하면 문제가 해결된다!

 

---

+a

 

원래는 반복문 안에서 배열을 제거하는게 불편해서, 새로운 배열에 대입한다.

하지만 값을 비교하는 반복은 대입하는 반복보다 수행횟수가 많아서 번거로운 방식이 된다.

 

answer의 초기화는 ① 이전에도 할 수 있으나, 이후에 하는 것이 불필요한 연산을 줄여준다.