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

문제

 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.

먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다.

문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

 

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

b aa baa → bb aa → aa → 

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

 

 

제한조건

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

 

 입출력 예

 

 

 

 

 

풀이

 이 문제는 위의 문제 설명과 같이 문자열의 공백을 제거 후, 같은 문자가 2회 반복되는 경우 제거하는 과정을 반복하여 모두 제거 가능하면 1, 그렇지 못한 경우 0을 리턴하는 문제입니다. 

문제를 보자마자 while문 내에 for문을 이용하여 2회 반복되는 문자열을 찾아 삭제하는 과정을 반복하면 쉽게 풀이를 할 수 있을 것이라 생각해서 다음과 같이 풀이를 진행해보았습니다.

 

1. 문자열의 공백을 제거해준다.

2. for문을 이용하여 2회 반복되는 문자열을 찾아 제거한 후, 확인을 위해 flag 값을 1로 바꾸어준다.

3. 이 과정을 while문을 이용하여 반복해주고, 문자열의 길이가 0이 된 경우나, 제거된 값이 없는 경우에 각각 1과 0을 리턴해준다.

 

def solution(s):
    s = s.replace(' ', '')
    while(1):
# s의 길이 -1 만큼 반복문 돌면서 같은 문자 2회 반복 시 제거
        for i in range(len(s)-1):    
            flag = 0
            if(s[i] == s[i+1]):
                s = s.replace(s[i]*2,'')
                flag = 1
                break;
                
# for문 반복될 때마다 제거된 문자 있는지 확인 후 길이가 0이면 1 리턴
# 더이상 제거할 문자 없는데 길이가 0이 아닌 경우 0 리턴
        if(flag == 0 and len(s) != 0):
            return 0
        if(flag == 1 and len(s) == 0):
            return 1

이렇게 코드를 작성 후 테스트를 진행하니 정상적으로 통과하였습니다. 그러나 제출 후 채점을 진행해보니

 

대부분의 테스트 케이스에서 시간초과가 발생하였습니다.

아마도 문자열 전체를 순서대로 찾고, 제거하는 과정을 계속 반복하는 것이다보니 시간 초과가 발생한 것 같습니다. 

 

그래서 다른 블로그 글들을 참고해보니 스택을 이용하는 방법이 있다는 것을 알게되었습니다. 스택을 이용하여 문자열의 각 문자를 스택에 넣어주면서 2회 반복되는 값이 있는 경우 제거하는 방식으로 풀이를 진행하였습니다.

 

1. 문자열의 공백을 제거해준다.

2. for문을 이용하여 문자열의 처음부터 문자 하나씩 스택에 추가해준다.

3. 스택에 값을 추가하기 전, 스택의 top 값과 현재 문자의 값이 같은 경우, 스택에 추가하지 않고 top 값을 pop 한다.

4. 최종적으로 스택이 비어있는 경우 1을 리턴 , 스택이 비어있지 않은 경우 0을 리턴해준다.

 

코드로 구현하면 다음과 같습니다.

def solution(s):
    s = s.replace(' ', '')    # 공백 제거해줌
    stack = []
    
    # 문자열 각 값이 스택의 top과 같은 경우 2회 반복되는 문자(제거)
    for i in s:
        if(len(stack) == 0):
            stack.append(i)
        elif(stack[-1] == i):
            stack.pop()
        else:
            stack.append(i)
    
    
    # 길이가 0 이면 1 리턴, 아닌 경우 0 리턴
    if(len(stack) == 0):
        return 1
    else:
        return 0

 

 

 

위와 같이 풀이를 진행하니 모든 테스트가 통과되는 것을 확인할 수 있었습니다.