[파이썬] 프로그래머스 알고리즘 고득점 Kit - 스택 / 같은 숫자는 싫어 완벽해설

문제

 

 

 

해설

 

이 문제는 스택(Stack)을 사용하라고 주어진 문제이다.

 

 

스택은 말 그대로 스택처럼 쌓는 자료 구조로 Last in first out (LIFO)의 구조를 지닌다. 그래서 마지막으로 들어간 값이 처음으로 나오는 그런 자료 구조이다.

 

스택을 사용하는 것에 대해서 특별히 유리한 장점은 따로 존재하지 않지만, 우리가 경험하는 것들 중 몇몇 부분들은 스택으로 구현이 되어 있다. 예를 들면 우리가 인터넷을 할 때에 뒤로가기를 누르면 그 전에 방문한 웹사이트로 가지게 된다. 즉 우리가 사용하는 브라우저의 웹 방문기록은 스택 방식으로 구현이 되어 있기 때문이다. 그 외에도 재귀 함수를 사용할 때에도 스택이 사용될 수도 있다.

 

아무튼 이 문제의 경우 딱히 스택의 용도를 전체적으로 활용하라고 주어진 문제는 아니고, 파이썬에서 스택은 곧 리스트랑 거의 비슷한 자료구조를 지니기 때문에 단순히 리스트를 잘 활용하라는 의미에서 주어진 문제인 것 같다.

 

이 문제의 코드는 "투 포인터 알고리즘"을 활용하면 정말 쉽게 코드를 짤 수가 있다.

 

arr 배열에 대해서 앞에서 뒤로 순서대로 하나하나 지목하는 원 포인터를 두고, 그 외에 다른 하나의 투 포인터를 둔다. 투 포인터는 중복된 값을 판단하기 위한 포인터로 둔다. 투 포인터는 하나의 숫자를 지목하고 있고, 원 포인터가 하나하나 순서대로 지나가면서 투 포인터가 지목하는 숫자와 비교하게 된다. 만약 이 두 포인터가 지목하는 숫자가 같을 경우에는 아무 조작도 하지 않고, 다를 경우에만 그 다른 숫자들을 기록해두고, 투 포인터로 하여금 그 다른 숫자를 다시 지목하도록 하고, 원 포인터는 계속 나아가면서 똑같은 행동을 반복하도록 해주는 코드를 구현해주면 된다.

 

 

코드

def solution(arr):
    answer = []
    dual_pointer = 0
    answer.append(arr[0])
    for i in range(1, len(arr)):
        if (arr[i] != arr[dual_pointer]):
            dual_pointer = i
            answer.append(arr[dual_pointer])
    return answer

 

 

결과