[스택] 같은 숫자는 싫어

https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

def solution(arr):  
    answer = []
    stack = []

    for i in range(len(arr)):
        if stack and arr[i] != arr[stack[-1]]:
            answer.append(arr[stack[-1]])
            stack.clear()

        stack.append(i)

    answer.append(arr[stack[-1]])

    return answer

 

배열 크기가 최대 1,000,000의 자연수이기 때문에 이중  for문을 사용한 O(n^2) 접근 방법은 효율성 제한에 걸린다.

O(n)의 비용으로 솔루션을 얻기 위해 스택을 사용한다.

본 문제에서 사용한 로직은 stack에 계속해서 인덱스를 쌓아나가되,

이 인덱스에서 참조한 arr의 값이 새로 들어오는 값과 달라지게 되면 비교 대상인 수를 answer에 추가하면서 기존의 stack을 비운다.

 

입출력 예시에서

[1, 1, 3, 3, 0, 1, 1]

의 리스트를 입력받게 되면

 

stack에는 0, 1의 인덱스가 쌓이게 되고,

최초로 3이 들어오게 될 때 arr[stack[-1]]에 해당하는 값인 1을 answer에 추가하고 stack을 비운다.

 

이후 stack에는 다시 2, 3의 인덱스가 쌓이고,

최초로 0이 들어올 때 마찬가지로 arr[stack[-1]]에 해당하는 값인 3을 answer에 추가하고 stack을 비운다.

 

이렇게 계속해서 진행하게 되면 stack에는 마지막으로 추가해줄 인덱스만이 남게 되는데

이를 arr에서 참조해서 추가해주면 배열 크기 n만큼의 반복만으로도 모든 중복된 값을 제거할 수 있다.