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

문제 링크

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

프로그래머스

소스 코드

def solution(s):
    stack = []
    for idx in range(len(s)):
        if not stack: # 스택이 비어 있는 경우
            stack.append(s[idx])
        else: # 스택의 마지막 글자와 동일한 것이 들어오는 경우
            if stack[-1] == s[idx]:
                stack.pop()
            else: # 스택의 마지막 글자와 다른 글자가 들어오는 경우
                stack.append(s[idx])
    if stack: return 0 # 스택에 남은 글자가 있다면
    else: return 1 # 스택에 남은 글자가 없다면

해설

• 스택
• 시간복잡도 고려 필수

시간복잡도

문제의 설명을 보면 주어지는 문자열 s의 최대 길이는 1,000,000입니다.

길이가 굉장히 긴 문자열이 주어질 수 있으므로 이중 for문을 사용하거나 비효율적인 while문을 사용하게 되면 반드시 시간 초과 판정을 받게될 것입니다.

물론 그걸 알아도 아이디어가 없을 땐 일단 구현해봐야겠죠?

def solution(s):
    answer = -1
    chars = [chr(x)*2 for x in range(97,123)]
    
    while True:
        flag = False
        for char in chars:
            if char in s:
                s = s.replace(char,"")
                flag = True
        if not flag: break
    
    if not s: return 1
    else: return 0

맨 처음 시간 초과 판정을 받은 풀이입니다.

'aa', 'bb', ... 'zz' 까지 해당하는 문자쌍 리스트를 만들고, 문자열 s에 위 리스트의 원소가 존재하는 동안에는 계속해서 공백으로 바꿔줍니다.

while문이 종료되었을 때 문자열이 남아있다면 0을, 남아있지 않다면 1을 return 합니다.

 

이와 같은 풀이는 시간 복잡도가 너무 안 좋기 때문에 채점 시간 자체도 엄청 길더라구요.

따라서 우리는 반드시 문자열을 딱 한 번만 탐색하는 풀이를 고안해야 합니다.

 

이와 어울리는 자료구조는 stack(스택)입니다.

스택은 LILO(Last In Last Out) 구조를 가지고 있죠.

문제 예시를 살펴보겠습니다.

 

s = 'baabaa' , stack = [ ] 입니다.

1) 스택이 비어있으므로 b가 추가됩니다. ['b']

2) 스택이 비어있지 않지만 'a'와는 다르므로 또 스택에 추가됩니다. ['b', 'a']

3) 스택이 비어있지 않고 마지막 글자 'a'와 동일하므로 스택의 원소를 제거합니다. ['b']

4) 스택이 비어있지 않고 마지막 글자 'b'와 동일하므로 스택의 원소를 제거합니다. [ ]

5) 스택이 비어있으므로 a를 추가합니다. ['a']

6) 스택이 비어있지 않고 마지막 글자 'a'와 동일하므로 스택의 원소를 제거합니다. [ ]

 

결과적으로 스택은 완전히 비게 되어서 모든 문자열이 제거될 수 있다는 것을 알 수 있습니다.

 

요약하면 중간의 짝을 이루는 문자열을 제거하여 앞뒤를 연결해주는 것은 stack.pop을 해서 스택에 남아있던 원소와 새로 만나는 원소를 비교할 수 있게끔 해주는 것으로 구현할 수 있다는 것입니다.