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

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

코딩테스트 연습 - 짝지어 제거하기

 

< 문제 설명 >

주어진 문자열에서 알파벳이 같은 두 문자열 짝을 찾아 제거한다.

그리고 남은 문자열을 합치고, 제거하는 과정을 반복한다.

마지막에 문자열을 모두 제거하면 1을 리턴하고, 그렇지 않으면 0을 리턴한다.

 

 

< 문제 이해 >

처음에 중복된 문자열을 제거한다고 해서 정규표현식이 떠올랐다.

그래서 열심히 찾아보고 문제를 풀어봤는데 아무래도 시간 초과로 실패한다.

그래서 문자 하나하나 비교하는 방식으로 다시 풀었다.

 

 

< 문제 풀이1 > 실패

정규표현식을 사용한 풀이는 아래와 같다.

[a-z]는 소문자 영어 한 글자를 의미하고, ()는 그룹을 의미한다. 

따라서 ([a-z])는 소문자 알파벳 한 글자를 한 그룹으로 생각하겠다는 의미가 된다.

뒤에 \\1은 첫번째 그룹을 의미한다. 즉, 괄호로 묶여 있는 그룹 중 첫 번째 그룹의 값을 참조한다는 것이다.

따라서 ([a-z])\\1은 똑같은 문자 2개를 의미하기 때문에,

re.sub('([a-z])\\1','',s)는 똑같은 문자가 2개 나오면 공백으로 바꾸라는 의미가 된다.

 

([a-z])\\1{2} -> 소문자 알파벳 한 글자가 세 번 반복됨을 의미

([a-z])\\1{1:} -> 소문자 알파벳 한 글자가 두 번 이상 반복됨을 의미

import re
import math

def solution(s):
    before = ''
    
    while s != before:
        before = s
        s = re.sub('([a-z])\\1','',s)
        if len(s) == 0 : break

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

 

 

< 문제 풀이2 >

def solution(s):
    temp = []

    for i in s:
        if len(temp) != 0 :
            if temp[-1] == i:
                temp.pop()
                continue
        temp += i

    if len(temp) == 0 : return 1
    else : return 0

 

 

 

참고

https://dojang.io/mod/page/view.php?id=2438