[프로그래머스] Lv1. 같은 숫자는 싫어

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

접근

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

arr의 크기가 10^6이므로, 시간복잡도 O(n) 밑으로 풀어야 한다.

코드

def solution(arr):
    stack = []
    for a in arr:
        while stack and stack[-1] == a:
            stack.pop()
        stack.append(a)
    return stack

 

풀이

• 배열을 하나씩 탐색해서 만약 스택에 값이 있고, 가장 마지막으로 들어간 수가 a와 같을 경우 while문에 진입한다.
• 같은 수가 없을 때까지 스택을 팝 해주고 반복문을 나온다.
• 같은 수를 다 팝 했기 때문에 스택에 마지막으로 a를 한 개 넣어주고 다음 수로 넘어간다.