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

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

2017 팁스타운

1트

def solution(s):
    s = list(s)
    while s:
        c = s.copy()
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                del s[i:i+2]
                break
        if c == s:
            return 0
    return 1

시간 초과 발생


2트

def solution(s):
    s = list(s)
    while s:
        length = len(s)
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                del s[i:i+2]
                break
        if length == len(s):
            return 0
    return 1

copy 대신 길이로 비교하니까 시간 줄긴 했음
그러나 시간 초과 발생


3트

def solution(s):
    while len(s) > 0:
        length = len(s)
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                s = s[:i] + s[i+2:]
                break
        if length == len(s):
            return 0
    return 1

s를 list로 안 바꾸고 문자열 그대로 사용했더니 시간 많이 줄어듦
그래도 시간 초과 발생

근본적인 문제가 있는 거 같아서 검색으로 힌트를 얻었음
Stack을 사용하면 된다고 한다.
Last in First Out 의 성질을 기억하자

4트

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

    for i in s[1:]:
        stack.append(i)
        if len(stack) >= 2 and stack[-1] == stack[-2]:
            stack.pop(); stack.pop()
        else:
            continue
    if stack:
        return 0
    else:
        return 1

성공!
변수 개수를 줄여야된다는 강박이 좀 있었던 것 같다.
Stack으로 사용할 list를 하나 추가하니까 while문을 벗길 수 있었음

for문을 벗어난 뒤에 최종적으로 stack 리스트가 비어있지 않으면 0을, 비어있으면 1을 리턴한다.

def solution(s):
    answer = []
    for i in s:
        if not(answer):
            answer.append(i)
        else:
            if(answer[-1] == i):
                answer.pop()
            else:
                answer.append(i)    
    return not(answer)

차라리 이렇게 조건문을 조금 더 쓰는 게 코드가 더 직관적으로 보이는 것 같다.

다음 문제를 풀 때는 고려하자