[프로그래머스 Lv.2] 짝지어 제거하기 (Python)

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

프로그래머스

풀이

레벨 2 문제임에도 아이디어를 생각하는 것이 상당히 까다로운 문제였다.

문자열의 길이가 1000000개이기 때문에 파이썬이 초당 2000만 번의 연산을 한다는 것을 생각하면 O(n^2) 이하의 알고리즘으로 풀어야 한다.

그렇기에 O(n)이나 O(nlogn)으로 풀 수 있는 방법을 생각해야 하고, 그 방법으로 스택을 사용하였다.

아래의 코드와 같이 진행하면 O(n)의 시간복잡도를 보여 시간 내에 해결할 수 있다.

def solution(s):    
    stack = []
    for ch in s: # 문자열의 문자를 하나씩 순회하며
        if stack and stack[-1] == ch: stack.pop() # 배열이 빈 상태가 아니면서 배열의 가장 끝에 위치한 문자와 현재 문자가 일치한다면 가장 마지막에 있는 문자를 제거 
        else: stack.append(ch) # 그렇지 않다면 배열에 문자를 삽입
    
    return 1 if not stack else 0 # 최종적으로 배열이 비었다면 모두 짝지을 수 있는 것