Logo

같은 숫자는 싫어

프로그래머스의 같은 숫자는 싫어 문제를 함께 풀어보도록 하겠습니다.

문제

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

  • arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
  • arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

예제

Input: [1,1,3,3,0,1,1]
Output: [1,3,0,1]
Input: [4,4,4,3,3]
Output: [4,3]

풀이 1

문제를 자세히 읽어보지 않으면 중복 숫자를 제거하기 위해 무턱대고 집합(set) 자료구조를 사용하다가 낭패를 볼 수 있습니다. 첫째로, 세트 자료구조는 원소들을 순서없이 저장하지만 문제에서 원소들의 순서를 유지하라고 요구하고 있습니다. 둘째로, 단순히 중복 숫자를 제거하는 것이 아니라 연속되고 있는 중복 숫자를 제거하라고 요구하고 있습니다.

자, 그럼 세트를 쓰는 것을 포기하고 문제에 어떻게 접근할지 다시 생각을 해볼까요? 먼저 원소들의 순서를 유지하려면 입력 배열을 순차적으로 스캔하면서 선택적으로 결과 배열에 숫자를 추가를 해야될 것 같습니다. 그리고 동일한 숫자가 연속해서 나오는 구간이 있으면 그 중 딱 하나만 남겨야 합니다.

그럼 동일한 숫자로 이루어진 구간이 언제 시작하고 끝나는지가 중요할 텐데요. 구간이 시작할 때 한 번만 숫자를 결과 배열에 추가하고, 그 다음에 나오는 동일한 숫자들은 모두 건너띄어야하기 때문입니다.

         ___ ___ _ ___
Input:  [1,1,3,3,0,1,1]
         ↓   ↓   ↓ ↓
Output: [1,  3,  0,1  ]

동일한 숫자의 구간이 시작하는지 판단하려면 이전 숫자와 비교를 해야하는데요. 이전 숫자는 현재 인덱스에서 1일 뺀 자리에 있으므로 쉽게 접근할 수 있습니다. 그런데 현재 인덱스가 0일 때는 예외 상황이 발생하는데요. 첫 번째 숫자에게는 이전 숫자가 없으므로 무조건 결과 배열에 추가해야 합니다.

이 알고리즘을 파이썬으로 구현해보겠습니다.

def solution(arr):
    result = []
    for i in range(len(arr)):
        if i == 0 or arr[i - 1] != arr[i]:
            result.append(arr[i])
    return result

이 풀이는 입력을 배열을 한 번 루프르 돌고 있기 때문에 O(n)의 시간 복잡도를 가집니다. 공간 복잡도는 결과 배열의 크기는 무시하면 O(1)이 됩니다.

풀이 2

위 풀이에서는 이전 숫자를 얻기 위해서 입력 배열에 접근해었는데요. 사실 결과 배열에 가장 마지막에 추가된 숫자도 이전 숫자와 동일할 것입니다.

따라서 이러한 사실을 활용하면 인덱스로 루프를 돌지 않고 바로 값으로 루프를 돌 수 있어서 좀 더 깔끔한 코드를 짤 수 있습니다. 단, 결과 배열이 비어있을 때는 주의가 좀 필요합니다. 이 때는 무조건 숫자를 추가해야합니다.

def solution(arr):
    result = []
    for num in arr:
        if not result or result[-1] != num:
            result.append(num)
    return result

파이썬은 음수 인덱스를 지원하기 때문에 배열의 마지막 원소에 인덱스 -1로 접근할 수 있어서 편리합니다.

이 풀이의 복잡도는 이전 풀이 동일합니다.

풀이 3

이전 두 개의 풀이처럼 이전 숫자를 입력 배열이나 결과 배열에서 찾지 않고 그냥 변수에다가 저장해놓는 방법도 있는데요. 이럴 경우, 첫 번째 숫자인지를 조건문에서 반복적으로 확인하지 않아도 되기 때문에 코드가 좀 더 길어도 읽기다 좀 더 쉬울 수 있습니다.

def solution(arr):
    result = []
    prv = None
    for cur in arr:
        if prv != cur:
            result.append(cur)
        prv = cur
    return result

if 문에서 하는 일이 하나 줄었지만 의미있는 성능 차이가 있다고는 볼 수 없습니다. 어차피 빅오 계산법에 따라서는 여전히 O(n) 시간의 풀이이기 때문입니다.

마치면서

지금까지 다룬 3가지 풀이가 코딩 스타일만 약간씩 다를 뿐 기본적으로는 같은 접근 방법이라고 생각합니다. 배열을 순회하는 기본적인 요령을 익하는데 좋은 문제이오니 입문자들에게 추천드리고 싶습니다.