[프로그래머스] Lv2. 짝지어 제거하기

문제

풀이

• 완전한 브루트포스 방식으로 문자 두개가 같으면 pop을 하는 방식
• 테스트 케이스는 금방 통과했지만 제출하자마자 무한 시간초과

로직은 틀린 게 없다고 생각했는데 시간초과가 나서 너무 멘붕이었다. 힌트를 보니 스택을 사용하면 쉽게 풀린다고 해서 두 번째 멘붕이었다. 진짜 1도 생각 못한 방법이었음...

def solution(s):
    string = list(s)
    
    idx = 0
    while idx < len(string)-1:
        if string[idx] != string[idx+1]:
            idx += 1
            continue
        string.pop(idx)
        string.pop(idx)
        if idx != 0:
            idx -= 1
        print(string)
        
    if string:
        return 0
    return 1

스택을 사용한 풀이

스택은 First In Last Out 구조이며 한쪽으로만 데이터의 입/출력이 가능하다. 즉 가장 최근에(나중에) 들어간 데이터를 가장 빨리 빼낼 수 있기 때문에 바로 옆에 붙어있는 문자열들을 비교하기에 수월하다

우선 스택의 가장 최근에 저장된 값(stack[-1])이 현재 비교하려는 문자열과 일치하는지 확인해야 한다. 여기서 stack이 비어있을 수도 있기 때문에 두 개의 값을 둘 다 리스트로 만들어서 비교해줬다.

if stack[-1:] == [word]

만약 일치한다면 스택의 가장 최근에 저장된 값을 제거하고, 일치하지 않는다면 문자열을 스택에 추가하고 비교를 이어간다.

def solution(s):
    stack = [s[0]]

    for word in s[1:]:
        if stack[-1:] == [word]:
            stack.pop()
        else: 
            stack.append(word)

    if stack:
        return 0
    return 1

근데 이 방법은 시간이 엄청나게 걸렸다.

스택이 빌 일이 없도록 빈 문자열을 하나 추가하기

애초에 그냥 스택이 비지 않도록 앞에 빈 문자열을 하나 추가해주고 비교하면 되는 일이었다. 리스트로 바꿔 비교하는 부분만 바꿨을 뿐인데 시간복잡도가 1/2로 줄어들었다

def solution(s):
    stack = [" ", s[0]]

    for word in s[1:]:
        if stack[-1] == word:
            stack.pop()
        else: 
            stack.append(word)

    if len(stack) == 1:
        return 1
    return 0

후기

자료구조를 써야 한다는 생각자체를 못 떠올린게 너무 충격적