[프로래머스] 같은 숫자는 싫어 / 파이썬(Python)

https://programmers.co.kr/learn/courses/30/lessons/12906?language=python3 

코딩테스트 연습 - 같은 숫자는 싫어

 

문제 설명

 

배열 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 함수를 완성해 주세요.

 

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

 

입출력 예

 

arr	answer
[1,1,3,3,0,1,1]	[1,3,0,1]
[4,4,4,3,3]	[4,3]

입출력 예 설명

입출력 예 #1,2
문제의 예시와 같습니다.

 

---

풀이

 

def solution(arr):
    answer = []
    tmp = arr[0]
    answer.append(tmp)
    
    for i in arr:
        if i != tmp:
            tmp = i
            answer.append(i)
    return answer

 

사실 문제는 어렵지 않다. arr 배열을 탐색하면서 연속된 숫자는 한 번만 answer 배열에 담아주면 된다.

문제를 채점하고 보니 효율성을 채점하고 있었다. 나의 경우 한번에 통과했지만, 다른 사람들은 어떻게 풀었는지 궁금해 찾아보았다. 다른 사람들의 풀이들 중에서 기존의 arr 배열에서 원소를 삭제하는 방법을 고른 사람들이 여럿 있었고, 그 경우에 효율성을 통과하지 못한다고 했다. 그 이유는 다음과 같다.

 

기존 배열의 원소를 빼는 것보다 , 새 배열에 추가하는 방식이 더 빠른 이유?

 

1. 파이썬(Python)의 list 자료구조는 'stack'

 

자료구조는 크게 선입선출의 "queue"와 선입후출의 "stack"으로 나눌 수 있습니다. list는 stack 구조이므로 index 넘버가 작을수록 제거하는데 많은 연산양을 필요로 하게 됩니다. 예를 들어 길이가 100인 list에 대하여 pop(0) 함수를 호출하려면 , 가장 먼저 삽입된 0번 index의 원소를 제거하기 위해 100번의 연산을 필요로 합니다.

 

2. append()가 더 빠른 이유

 

append() 함수가 작동하는 방식에 대해서는 자세히 모르지만 , 적어도 새 배열에 옮기는 용도로 사용 할 경우에는 중복체크를 위해 이미 참조한 값을 복사하면 되므로 단 한 번의 연산만을 필요로 합니다.