[python 스택] 짝지어 제거하기 - 프로그래머스

 

솔루션

def solution(s):
	# 홀수일 경우 짝이 맞지 않음.
    if len(s)%2==1:
        return 0
    stack=[s[0]]
    i=1
    while i<len(s):
 		# 짝이 맞을 경우 pop
        while stack and stack[-1]==s[i]:
            stack.pop()
            i+=1

        if i<len(s):
            stack.append(s[i])
            i+=1

    return 0 if len(stack) else 1

 

이 문제에서 핵심은 효율성입니다. 인덱스로 풀거나, s에 담겨 있는 중복된 데이터를 pop 하려고 한다면 효율성에서 걸리게 됩니다. 중복된 데이터를 삭제하는 전략을 짰을 경우에 s에 대해서 선형 탐색을 실시하게 되는데 최악의 경우 s에 담겨있는 데이터의 절반만큼 반복해야 합니다.(선형 탐색 한번에 중복된 걸 한번씩 찾는 경우) 또한 앞에 있는 데이터를 삭제할 경우 뒤에 있는 모든 데이터를 앞쪽으로 옮겨와야 하기 때문에 수많은 계산을 요구하게 됩니다. 데이터를 삭제하지 않고 인덱스만을 택한다고 하여도 시간 초과가 발생하게 됩니다. 그 이유는 이런 방식으로 알고리즘을 짤 경우에 O(N^2)의 복잡도가 나오기 때문입니다.  

 

 python은 1초에 2000만번 계산을 하지만 이 문제의 s는 최대 100만개의 데이터를 갖고 있습니다. 따라서 O(N^2)의 복잡도가 나오는 이러한 방식은 최선이 아닙니다 .

 

이 문제에 적합한 자료구조는 스택입니다. O(N)으로 알고리즘을 짤 수 있고 위에서 설명한 방식보다 계산량이 훨씬 줄어들기 때문에 시간을 절약해줍니다. 스택은 아래에서부터 쌓아올리고 가장 나중에 쌓은 자료를 꺼내는 구조입니다. 따라서 글자를 쌓다가 같은 글자가 2개가 쌓이면 삭제해주는 방식으로 하다보면 s에 담긴 데이터만큼의 계산을 한 이후에 결과값이 나옵니다.