프로그래머스 - 배열 조각하기 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/181893#qna

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

vector<int> slice(int s, int e, vector<int>& ans)
{
    vector<int> a(e - s + 1);

    copy(ans.begin() + s, ans.begin() + e + 1, a.begin());
    return a;
}

vector<int> solution(vector<int> arr, vector<int> query) {
    vector<int> answer = arr;

    for (int i = 0; i < query.size(); i++)
    {
        if (i % 2 == 0)
        {
            answer = slice(0, query[i], answer);
        }
        else
        {
            answer = slice(query[i], answer.size() - 1, answer);
        }
    }

    return answer;
}

int main()
{
    vector<int> r = { 0, 1, 2, 3, 4, 5 };
    vector<int> a = { 4, 1, 2 };
    solution(r,a);

    return 0;
}

 

설명

짝수 인덱스에서는 query[i] 번 인덱스 뒤의 원소들을 없애고

홀수 인덱스에서는 반대로 query[i]번 전까지의 원소들을 없애며 배열을 만든다.

 

이 때, 사용하면 편리한 함수가 copy() 함수이다.

copy(arr.begin(),arr.begin()+5,copyArr.begin());

 

첫번째 인자와 두번째 인자는 어디서부터 어디까지를 복사해줄건지 반복자를 각각 대입해준다.

세번째인자는 복사받을 반복자의 시작위치이다.

 

slice 함수를 따로 만들어 인덱스를 넘겨주면 vector<int>로 반환하게 하여 짝수, 홀수의 경우에 맞춰서 인덱스를 넘겨주었다. 

이 문제는 최대 10만개의 원소를 가진 arr이 가능하다. 그래서 위와 같은 방법을 값에 의한 호출 방법으로 사용하게 되면 훨씬 느리게 동작하게 된다. 함수를 호출할 때마다 몇만번씩 복사가 이뤄지기 때문이다. 따라서 참조 연산을 활용하였다. 

 

처음엔 아예 간단한 연산으로만 풀어보기 위해서 변수 몇개만으로 현재 원본배열 arr에서 query에 의해 만들어진 배열의 시작위치와 끝위치를 계산해보려고 했지만 쉽지 않아서 다른방법을 사용하였다.