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

문제 링크

---

1. 아이디어

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

---

2. 복잡도

접근	시간	공간
인접 비교	$O(N)$	$O(N)$
groupby	$O(N)$	$O(N)$

($N$ = 배열 arr의 길이)

---

3. 코드

풀이: 인접 비교 [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):
    lst = []
    for x in arr:
        if not lst or lst[-1] != x:
            lst.append(x)

    return lst

---

풀이 2: groupby [Python]

itertools.groupby는 연속된 동일 값을 자동으로 그룹핑해 주므로, 인접 원소를 직접 비교하는 반복문 없이도 각 그룹의 대표값만 뽑으면 같은 결과를 얻을 수 있다.

from itertools import groupby


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

---