[Programmers] L2. 짝지어 제거하기 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

💡 스택 이용

 

스택이 비어있으면 스택에 값을 넣는다.

스택의 맨 마지막 요소가 현재 문자와 같으면 꺼낸다.

위 조건이 다 맞지 않으면 스택에 현재 문자를 넣는다. 

 

Solution

def solution(s):
    stack = []
    for i in s:
        if not stack:  # 스택이 비어있으면
            stack.append(i)
            continue

        if stack[-1] == i:  # 스택 맨 뒤 요소와 같으면
            stack.pop()
            continue
            
        stack.append(i)  # 위 조건이 모두 맞지 않으면
    return 0 if stack else 1

 

---

👩‍💻 회고

시간 초과 난 코드

def solution(s):
    s = list(s)
    i = 1
    while True:
        if s[i - 1] == s[i]:
            s[i - 1], s[i] = '', ''
            i = 0  # 초기화
            s = list(''.join(s))
        if i >= len(s) - 1:
            break
        i += 1

    return 1 if len(s) == 0 else 0

 

시간 초과가 발생한 이유

s = list(''.join(s)) 구문에서 문자열 재구성을 반복적으로 수행하기 때문이다. 이 과정은 매번 전체 리스트를 문자열로 합친 후 다시 리스트로 변환하므로, O(n) 복잡도가 반복되어 시간 복잡도가 O(n²) 수준으로 증가하게 된다.

 

 

solution 코드와 주요 차이점

1. 리스트 재구성의 유무
   • 개선 전 코드(solution(s)) : 문자열을 합치고 리스트로 변환하는 과정을 반복하여 s = list(''.join(s))로 계속 전체 문자열을 조작한다.
   • 개선 후 코드(스택 사용) : 스택을 사용하여 한 번씩만 확인하고, 붙어있는 문자가 나오면 pop으로 제거하므로 전체 문자열을 반복해 재구성하지 않는다.
2. 시간 복잡도
   • 스택을 이용한 코드 : O(n)으로, 문자열을 단 한 번씩만 확인하면서 붙어 있는 쌍을 제거해 나간다.
   • 리스트 재구성 반복 코드 : O(n²)으로, 문자열을 재구성하는 과정이 반복될 때마다 더 많은 시간이 소요된다.

스택 구조를 이용하는 방식이 문자열을 재구성하는 방식보다 훨씬 빠르게 작동하므로, 스택을 사용한 코드가 훨씬 효율적이다.

---