[Programmers] #12906 - 같은 숫자는 싫어 [Java][C++][Python]

문제 링크

---

1. 아이디어

배열에서 지워야 하는 대상은 서로 인접한 위치에서 반복되는 숫자뿐이다. 같은 숫자라도 떨어져 있으면 그대로 남기고, 바로 옆에 연달아 나오는 경우에만 하나로 합친다. 그러므로 배열을 앞에서부터 한 번 순회하면서 직전에 결과에 추가한 값과 현재 값을 비교해, 서로 다를 때만 결과에 추가하면 된다. 이러면 매 원소를 한 번씩만 확인하고도 연속된 중복을 전부 걸러낼 수 있다.

---

2. 복잡도

접근	시간	공간
이전 값 비교	$O(N)$	$O(N)$
표준 라이브러리	$O(N)$	$O(1)$

($N$ = arr의 길이. Python은 새 리스트를 만들어 반환해 표준 라이브러리 방식의 공간 $O(N)$)

---

3. 코드

풀이 1: 이전 값 비교 [Java][C++][Python]

import java.util.*;

public class Solution {
    public int[] solution(int[] arr) {
        List<Integer> list = new ArrayList<>();
        int prv = -1;

        for (int x : arr) {
            if (x == prv) continue;
            list.add(x);
            prv = x;
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> v;
    for (int x : arr) {
        if (v.empty() || v.back() != x) v.push_back(x);
    }

    return v;
}

def solution(arr):
    res = []
    for x in arr:
        if not res or res[-1] != x:
            res.append(x)

    return res

---

풀이 2: 표준 라이브러리 [C++][Python]

연속된 동일 값을 묶어 주는 표준 라이브러리 함수를 쓰면 인접 원소를 직접 비교하는 반복문 없이 같은 결과를 얻을 수 있다.

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> arr) {
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    return arr;
}

std::unique는 연속된 중복 원소를 뒤로 밀어내고 유효 구간의 끝 이터레이터를 돌려준다. 이 이터레이터부터 끝까지를 erase로 잘라내면 연속 중복이 제거된 배열만 남는다.

from itertools import groupby


def solution(arr):
    return [k for k, _ in groupby(arr)]

groupby는 연속된 동일 값을 자동으로 그룹핑하므로, 각 그룹의 대표값만 뽑으면 같은 결과를 얻을 수 있다.

---