250915 언리얼엔진 본캠프 30일차 벡터의 erase, remove함수

문제의 발단

오늘은 프로그래머스의 코드테스트 문제를 풀던 중 erase와 remove를 사용한 문제를 풀면서 공부한 내용을 정리해볼까 한다. 문제는 '제일 작은 수 제거하기' 문제로 그 내용은 다음과 같았다. 

"벡터가 주어졌을 때 가장 작은 수를 제외한 벡터를 반환하는 함수를 요구사항에 맞추어 작성할 것"

요구사항으로는 가장 작은 원소를 제거했을 때 벡터가 비게 된다면 '-1'을 채워 넣어 반환해야 한다. 인덱스 i와 j가 다르다면 arr [i] =/= arr [j]이다. 이 문제를 풀기 위해서 처음엔 다음과 같은 구조를 생각하게 되었다.

 

1. 인자로 받은 벡터 arr를 answer에 대입

 

2. answer를 sort함수를 이용하여 내림차순으로 정렬

 

3. answer에 pop_back을 적용하여 맨 마지막 수를 제거

 

4. 반환 이전에 if문을 이용해 빈배열일 경우 -1을 push_back한 후 반환

 

5. 아닐경우 answer 반환

 

그렇기에 다음과 같이 코드를 작성해 둔 상태였다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> answer=arr;
    sort(answer.rbegin(), answer.rend());
    answer.pop_back();

 

와 나 천재인가? 하면서 테스트를 진행해보니 통과되었다. 하지만 채점과정에서는 모두 통과하지 못하는 것 아닌가? 왜 그런 일이 발생했을까? 이유는 바로 내림차순에 있었다. 우연히도 테스트 샘플에는 [4, 3, 2, 1]과 [10] 두 가지의 벡터가 제공되는데 이는 이미 내림차순이 적용되어 있어 pop_back을 통해 제일 뒤의 수를 제거해도 원래 벡터의 원소 순서가 바뀌지 않은 채 [4, 3, 2]와 [-1]을 반환하여 테스트에는 통과가 가능하지만 실제 문제에서는 [1, 3, 4, 2]와 같이 순서가 뒤죽박죽 섞인 벡터가 인자로 들어오기에 위의 과정처럼 내림차순을 적용하여 반환하면 [4, 3, 2]가 되어 문제에서 원하는 정답이 아니게 되는 것이다. 그렇기에 나는 위의 방식을 조금 수정하여 다음과 같이 구조를 짰다.

 

1. 인자로 받은 벡터 arr를 answer에 대입

 

2. answer를 sort함수를 이용하여 내림차순으로 정렬

 

3. int자료형의 num에 answer배열의 가장 끝 수를 대입

 

4. arr배열에서 num에 해당하는 숫자를 제거

 

5. answer에 arr를 다시 대입 후 반환

 

6. 반환 과정에 if문을 이용해 빈배열일 경우 -1을 push_back한 후 반환

 

arr을 복사한 answer을 내림차순 정렬하여 가장 작은 숫자를 찾아주고 이 숫자를 원본 arr에서 찾아서 제거해 준 다음 answer에 대입해서 반환을 하는 방식을 생각했다.(사실 arr 자체를 반환해도 되겠지만) 그래서 코드를 다음과 같이 짜두었다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> answer=arr;
    sort(answer.rbegin(), answer.rend());
    int num = answer.back();

 

일단 인자를 받은 answer에서 제일 작은 값을 num에 대입하는것 까지는 하겠는데 그다음이었다. 원본 arr에서 num을 찾아 지워야 하는데 어떻게 해야 하지? 지운다? remove라는 게 있었던 것 같은데?라는 의식의 흐름으로 어떻게 remove까지 닿는 데는 성공했지만 그 사용법을 잘 알지는 못했다. 예전에 살짝 봤던 기억으로

remove(vector.begin(), vector.end(), target)

이런 식으로 썼던 것 같은 기억이 있어서 다음과 같이 작성해 보았다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> answer=arr;
    sort(answer.rbegin(), answer.rend());
    int num = answer.back();
    remove(arr.begin(), arr.end(), num);
    
    if(arr.size() == 0)
    {
    	arr.push_back(-1);
    }
    answer = arr;
    return answer;

 

하지만 테스트는 여전히 실패한다. 그야 당연하다 remove는 대상 숫자를 단순히 벡터에서 지우는 함수가 아니기 때문이다.

 

remove()?

자 서론이 길었다. remove 함수에 대해서 알아보자. remove는  위에서 말한 것처럼 대상 숫자를 벡터에서 지우는 동작을 하지 않는다. 인자를 하나씩 살펴보자

remove(vector.begin(), vector.end(), target)

 

remove가 호출되면 인자에 받은 값 처럼 해당 벡터의 시작부터 해당 벡터의 끝까지 타깃을 찾는다. 물론 시작지점과 끝 지점은 begin() + n 에서부터 begin() + m과 같은 형태로 프로그래머가 임의로 지정 가능하니까 사실은 다음과 같을 것이다.

remove(시작 위치, 끝내는 위치, 목표 값)

 

문제는 그 다음이다 remove가 타깃을 찾는 데 성공한다면 그 타깃을 지우고 그 뒤의 숫자들을 빈자리에 덮어 씌워버린다. 예컨대 [1, 3, 4, 6, 5]라는 벡터에서 3이라는 타깃을 대상으로 remove를 실행하면 [1, 4, 6, 5,?]의 형태가 되는 것이다. 문제는 여기서 발생한다 remove는 벡터의 크기를 바꾸지 않는다. 따라서 remove를 실행해서 3이라는 숫자는 지워졌지만 (사실은 지우는게 아니라 다음 숫자로 덮어 씌우는 거지만) vector의 size는 줄지 않은 채 그대로 5를 유지하기에 저? 에는 쓰레기값이 위치하게 된다. 그렇기에 위에서 작성한 코드대로 answer를 반환하게 된다면 쓰레기 값을 포함한 벡터가 반환되기에 틀리게 되는 것이다.

 

여기서 등장하는 그 이름도 찬란한 erase()

하지만 우리는 절반이나 해답에 도달했다. 위의 코드를 실행해서 우리는 어쨋든 타깃을 벡터에서 원래의 순서를 유지한 채로 없앤 [1, 4, 6, 5,?]라는 벡터를 획득했다 이제? 에 위치한 쓰레기값을 없애주면 되는데 우리는 특정 구간의 원소를 벡터에서 지우고 벡터의 크기도 줄여주는 erase() 함수를 배운 적이 있다.

vector.erase(시작 위치, 끝 위치);

erase는 다음과 같이 작성할 수도 있으며 말 그대로 지정한 시작위치부터 끝 위치까지의 모든 원소를 삭제하고 삭제된 크기만큼 원본 벡터의 size가 줄어들게 된다 그렇기에 우리는 erase함수와 remove함수를 섞어서 사용해줘야 한다.

vector.erase(remove(vector.begin(), vector.end(), target), vector.end());

 

이런 식으로 erase와 remove를 같이 사용하는 방식을 erase-remove idiom이라고 한다. 그럼 여기서 들 수 있는 의문이 "erase는 시작위치랑 끝위치를 받아서 그 구간을 지운다면서? 저 인자에 remove를 받을 수 있어?"일 것이다. 이런 의문이 드나? 싶을 수 있지만 내가 그랬다.(...) 우리가 기억해내야 할 것은 remove가 함수라는 것이다.

c++에서 함수라 하면 무엇인가? 반환값이 있어야 한다. remove는 앞서 말했듯 타겟을 찾아내 그 자리를 뒤의 숫자들로 덮어쓰고 맨 뒤에 쓰레기 값을 두는 것은 함수의 동작일 뿐이고 remove는 함수이기에 무엇인가를 반환해야 한다. 여기서 remove는 유효 데이터의 끝을 가리키는 반복자를 반환한다. 즉 아까의 예시로보면 유효데이터의 다음 자리인?를 가리키는 반복자를 반환한다. 그렇기에 erase는? 자리부터 vector의 끝까지의 구간을 모두 지우고 그만큼 벡터의 크기를 줄이는 동작을 수행하게 되어 우리가 원하는 결과를 얻을 수 있게 된다. 참고로 erase는 마지막으로 지운 요소의 다음 위치를 반환하며 만약 끝까지 지웠다면 end()에 해당하는 위치를 반환하게 된다.

그렇게 최종적으로 작성한 코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> answer=arr;
    sort(answer.rbegin(), answer.rend());
    int num = answer.back();
    arr.erase(remove(arr.begin(), arr.end(), num), arr.end());
    if(arr.size() == 0)
    {
        arr.push_back(-1);
        return answer = arr;
    }
    else
    {
        answer = arr;
        return answer;
    }
}

 

마치며

사실 프로그래머스에서는 답안을 제출 후 다른 프로그래머가 작성한 답안을 확인할 수 있는데 내가 작성한 최종 코드보다 더 간략하고 다양한 함수를 사용해서 콤팩트한 코드를 작성한 굇수들이 득실득실하다는 것을 알 수 있다. 나도 꾸준히 공부해서 언젠가 저들처럼 콤팩트하면서도 실용적인 코드를 작성할 수 있을 때까지 노력해야겠다는 생각이 드는 날이다. 오늘 배운 remove의 작동 원리와 erase-remove idiom을 꼭 복습하면서 하루를 마무리하도록 하자.