짝지어 제거하기

 

프로그래머스

💡 생각

❌ 입력 문자열의 길이만큼 while 돌려놓고
그 안에서 for 돌면서 같은 문자가 연속되는지 검사,
연속된다면 반복 문자열이 빠진 새로운 문자열 만들고 for 탈출,
다음 while로 넘어가서 만들어진 새로운 문자열로 for 돌면서 같은 문자 연속되는지 검사 반복
1. 탈출했는데 기존 문자열과 만들어진 문자열이 같다
= 더 이상 지울 게 없음 return 0
2. 만들어진 문자열이 비어있다
= 다 지워짐 return 1
3. 둘 다 아님
= 다음 while문 돌기

def solution(s):
    # 1. 짝 찾기
    # 2. 짝 제거하기
    # 3. 1~2 반복하기

    new = s # new = baabaa
    index = len(s)

    while index != 0:
        print('while문 시작 s : ', s, ' new : ', new)
        s = new
        for i in range(1, len(s)):
            print('for문 시작 s[i-1] : ', s[i-1], ' s[i] : ', s[i])
            if s[i-1] == s[i]:
                new = s[:i-1] + s[i+1:]
                print('for문 중간 s : ', s, ' new : ', new)
                break
        print('while문 끝 s : ', s, ' new : ', new)
        if s == new:
            return 0
        elif new == '':
            return 1
        else:
            index -= 1
        print('==========================================')
    # return new

#     s1 = list(s)
#     s2 = list(s)
#     for i in range(1, len(s1)):

#     return list(s)

 

답은 맞지만 엄청난 시간초과 줸장

❌ replace로 새 코드도 짜봤지만 시간 초과가 더 심해졌땅

def solution(str):
    for s in str:
        new = str.replace(s+s,'')
    for n in new:
        new = new.replace(n+n, '')
    return 1 if new == '' else 0

 

❌ 흠.. 반복되는 문자들로 쪼개서 붙이는 방법도 효율성 테스트에서 통과를 못했다

def solution(str):
    for s in str:
        str = ''.join(str.split(s+s))
    return 1 if str == '' else 0

 

❌ str에 포함되는 문자들의 중복을 제거한 set 형태로 for문을 돌리면 빠르긴 한데 baabaa 같이 한 번 더 돌려야되는 경우 답이 틀린다

def solution(str):
    _set = set(str)
    for s in _set:
        str = ''.join(str.split(s+s))
    return 1 if str == '' else 0

 

❌ 총 알파벳 수가 26이므로.....? 26번까지만 해보자 (str%26도 해봤다) 정확성 45.3, 효율성 24.9 좀 오르긴 했음 일단 그리고 시간 초과가 안난다
왜 틀리는지 잘 생각해보자

def solution(str):
    index = 26
    while index != 0:
        _set = set(str)
        for s in _set:
            str = ''.join(str.split(s+s))
            if str == '':
                return 1
        index -= 1

    return 0

 

너무 오래 붙잡고 있어서 질문하기 쪽을 보니.. 스택으로 푸는 거라 한다 으앵 ...
방법을 아니 deque 를 사용해 쉽게 풀 수 있었다

 

📖 내 코드

from collections import deque

def solution(s):
    dq = deque(s[0])
    # print(dq)
    for i in range(1, len(s)):
        if dq and (s[i] == dq[-1]):
            dq.pop()
            # print(dq)
        else:
            dq.append(s[i])
            # print(dq)
    return 1 if len(dq) == 0 else 0

 

📑 다른 사람의 풀이

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)

 

보고 고칠 점이라면 1 if len(dq) == 0 else 0 이 부분을 int(not(dq))로 바꾸는 정도?? 왜 스택 쪽으로 생각을 못했을까 힝