프로그래머스 같은 숫자는 싫어 C++

https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

 

프로그래머스의 스택/큐 문제인데 주어진 배열에서 연속적으로 나타나는 숫자들을 제거하고, 나타난 순서대로 유지하여 반환하는 함수를 구현하는 문제입니다.

 

이런 배열이 있다고 칩시다.

 

 

해당 배열에 존재하는 '연속적으로 같은 숫자가 들어있는 경우'는 3가지로 1,3,1이 있습니다. 이 것을 프로그래밍적으로 어떻게 뺄까?

 

저는 스택/큐 문제니까 스택으로 풀어보려고 했습니다.

그런데 이럴수가, 만들어보니까 스택은 후입선출 구조기 때문에 넣고 바로 전 원소와 현재 원소를 비교하는 것은 빠르지만 꺼낼 때 반대로 정렬되게 됩니다.

 

 

그래서 큐를 사용해 배열을 비교해 큐에 넣을 것들을 골라 추가했습니다.

num.push(arr[0]);
for(int i = 1; i<arr.size(); i++){
    if(arr[i-1] != arr[i])
        num.push(arr[i]);
}

 

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;

    queue<int> num;
    num.push(arr[0]);
    for(int i = 1; i<arr.size(); i++){
        if(arr[i-1] != arr[i])
            num.push(arr[i]);
    }
    
    while(!num.empty()){
        answer.push_back(num.front());
        num.pop();
    }

    return answer;
}

 

이 문제를 푸는것 자체는 쉬웠는데 '연속적으로 나타나는 숫자는 제거하고 남은 수들을 return' 이 문구를 보자마자 아! 해시를 써서 중복을 제거하면 되겠다! 라고 생각해버려서 Set을 사용해 문제를 잘못 풀었던 경험이 있습니다. '연속적'을 '중복'이라고 생각해버려 생긴 문제로 테스트케이스를 돌려보다가 첫 번째 테스트 케이스의  답 [1,3,0,1]이 [1,3,0]으로 나와서 그제야 문제를 다시 봤습니다.

결국 맞추긴 했지만 다음부터는 문제를 꼼꼼하게 잘 읽어야겠습니다...

 

---

 

다른 사람들으 이 문제를 어떻게 풀었는지 궁금해서 봤는데 엄청난 풀이를 봤습니다.

 arr.erase(unique(arr.begin(), arr.end()),arr.end());

 

unique가 뭔지 궁금해서 찾아봤더니 범위 내에 연속적으로 존재하는 함수를 삭제하는 데 사용한다고 합니다.

정확히는 unique 함수가 vector 배열에 연속적으로 존재하는 값들을 배열 뒤에 쓰레기 값으로 몰아두고 그 값이 시작되는 부분을 반환한다고 합니다.

그래서 그 시작부분과 끝부분까지 지우는 방식으로 하는 것 같습니다.