[프로그래머스] 체육복, 벡터 삭제 시 주의점 (iterator, erase)

체육복

오늘은 체육수업이 있는 날입니다. 그런데 점심시간에 도둑이 들어 몇몇 학생의 체육복이 도난을 당했습니다. 다행히 일부 학생들이 여벌의 체육복을 가져왔습니다. 학생들의 번호는 체격 순으로 매겨져 있기 때문에 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려주려고 합니다.

예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 당연히 체육복을 2벌 가져온 학생의 체육복이 도난을 당했다면, 여벌의 체육복을 빌려줄 수 없습니다.

체육복이 없으면 체육수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 듣고 싶습니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

이 문제는 문제 설명이 문제를 더 어렵게 만든다. 핵심만 말하자면 lost 배열의 값을 reserve 배열의 값과 잘 비교해서 지워나가면 된다. 비교해서 지워 나간 뒤 lost 배열 남아있는 학생이 체육복이 없는 학생이므로 체육수업을 들을 수 있는 학생의 수는 n - lost.size()가 된다.

체육수업을 들을 수 있는 학생의 최댓값을 구하라고 해서 괜히 어려워 보이기도 한다. n번째 학생에게 체육복을 빌려줄 수 있는 학생은 n-1, n, n+1 학생이다. 지금 당장 노트를 펴서 연필로 간단히 숫자를 나열하기만 해도 n번째 학생에게는 n-1학생이 체육복을 빌려주는 게 제일 좋다는 것을 알 수 있다.

---

vector::erase(), iterator 와 주의점

벡터에는 특정 위치의 요소를 제거하고, 제거된 요소 수만큼 크기가 줄어드는 효율적인 erase() 메서드가 있다.

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

첫 번째 메서드의 경우 position 위치의 원소를 제거하고, 두 번째 메서드는 first부터 last 이전까지의 모든 원소를 제거한다. [first, last) 즉, 해당 위치의 원소를 제거하고 그 뒤에 있는 원소들을 남은 자리만큼 앞으로 이동시킨다. 이 특징은 반복문에서 iterator가 원하는 인덱스를 건너띄어 엉뚱한 곳을 참조할 수 있으므로 주의해야 한다.

반환 값인 iterator는 erase() 함수 호출에 의해 지워지는 요소의 다음 위치다. 이 반환 값을 이용해서 다음과 같이 벡터 A에서 값이 2인 요소를 모두 지우는 반복문을 프로그래밍할 수 있다.

std::vector A {1, 2, 2, 3, 4, 5};

// 벡터 A에서 값이 2인 요소를 모두 지우는 반복문
for (auto it = A.begin(); it != A.end(); )
{
    if (*it == 2)
    {
        // A.erase(it);
        // ++it -> 잘못된 방법! (다음 위치를 건너띄게 된다.)

        it = A.erase(it);
    }
    else
    {
        ++it;
    }
}

---

아래는 '체육복' 문제의 풀이다. isErase 플래그를 이용해서 ++it 사용에 조건을 두었다.

int solution(int n, vector<int> lost, vector<int> reserve) 
{    
    int num, number;
    bool isErase;
    for (auto it = lost.begin(); it != lost.end();)
    {
        num = *it;
        isErase = false;
        for (auto itt = reserve.begin(); itt != reserve.end(); ++itt)
        {
            number = *itt;
            if (num - 1 == number || num == number || num + 1 == number)
            {
                it = lost.erase(it);
                reserve.erase(itt);
                isErase = true;
                break;
            }
        }

        if (isErase == false) ++it;
    }

    return n - lost.size();
}

---

2018/12/19 - [프로그래머스] 소수의 합, 소수 판별 알고리즘

2018/12/21 - [프로그래머스] 완주하지 못한 선수

2018/12/23 - [프로그래머스] N으로 표현

2018/12/23 - [프로그래머스] 모의고사

2018/12/23 - [프로그래머스] K번째수