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

chanyeong kim·2021년 11월 28일

목록 보기

20/51

📩 -->문제설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.

입출력 예

s	result
baabaa	1
cdcd	0

💡 solution(사용언어: python)

첫 번째 방법

lower=['aa','bb','cc', 'dd', 'ee','ff','gg','hh', 'ii', 'jj', 'kk', 'll', 'mm', 'nn', 'oo', 'pp', 'qq', 'rr', 'ss', 'tt', 'uu', 'vv', 'ww', 'xx', 'yy', 'zz']
def check(string):
    new_string=string
    for i in range(0,len(string)):
        try:
            if string[i]==string[i+1]:
                new_string=new_string.replace(string[i:i+2],'')
            else:
                continue
        except:
            pass
    return new_string

def solution(s):
    while True:
        s=check(s)
        if any(i in s for i in lower):
            continue
        else:
            break
    if len(s)==0:
        return 1
    else:
        return 0

1) 입력받는 문자열과 똑같은 new_string을 만들어준다.
2) 기존 string의 앞 뒤를 비교해서 같으면, new_string을 replace를 이용해서 지워준다.
3) 2번 3번 과정을 갖게하는 함수 'check'를 만들어 준다.
4) if any를 이용해서 lower에 있는 요소들이 하나라도 문자열 s에 속하면 check를 반복해준다.

lower=['aa', 'bb', 'cc', ................'zz']

이 방법은 효율성을 통과하지 못한다...
아무래도 while과 for 문이 중첩되었기 때문인 것 같다!

두번째 방법

def solution(s):

    string = []

    for i in s:
        if len(string) > 0 and string[-1] == i:
            string.pop()
        else:
            string.append(i)

    if string:
        return 0
    else:
        return 1

👉 설명

1) string이라는 리스트를 선언해준다.
2) 입력받는 문자열에서 알파벳을 하나씩 뽑는다
3) string의 길이가 0보다 크고 string의 마지막 글자가 알파벳과 같다면, string 리스트의 마지막 글자를 지어준다.
4) 3번이 아니라면 string에 알파벳을 넣어준다.