[프로그래머스] 같은 숫자는 싫어 (Lv.1)

---

문제 링크

---

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

문제 설명

---

배열 arr에서 연속으로 나타나는 같은 숫자를 제거하고 남은 배열을 반환한다.
순서는 유지되며, 연속이 아닌 중복은 제거하지 않는다.

예) [1, 1, 3, 3, 0, 1, 1] → [1, 3, 0, 1]

내 풀이

---

unique + erase 패턴을 활용했다. unique()는 연속된 중복을 앞으로 밀어넣고 “쓰레기 구간”의 시작 iterator를 반환하므로, erase()로 그 구간을 잘라내면 연속 중복이 제거된 배열이 완성된다. 이후 range-based for문으로 answer에 복사해 반환했다.

#include <vector>
#include <algorithm>

using namespace std;

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

    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    
    for(int temp : arr)
        answer.push_back(temp);

    return answer;
}

시간복잡도 분석

---

| 연산 | 복잡도 | 이유 | |——|——–|——| | unique() | O(n) | 배열을 한 번 선형 순회 | | erase() | O(n) | 쓰레기 구간 삭제 시 뒤 원소 앞으로 이동 | | range-based for | O(n) | answer에 복사 | | 전체 | O(n) | |

arr의 최대 크기가 1,000,000이므로 O(n)은 충분히 통과 가능하다.

후기

---

풀고 나서 보니까 굳이 answer에 다시 값을 넣지 않고 그대로 arr을 반환했어도 됐다는 걸 알았다.
굳이 필요하지 않으면 빼자.

• algorithm
• codingtest
• stack