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

문제

 

틀렸던 풀이(시간 초과)

#짝지어진 문자열을 제거하는 함수 정의
def rm_pair(s):
	#중복 방지를 위해 set() 사용
    c_set = set()
    #짝지어 제거하기이므로 문자 * 2 해서 set에 넣음
    for c in s :
        c_set.add(c * 2)
    
    for pair in c_set :
        s = s.replace(pair, '')
        
    return s

def solution(s):
    
    while True:
        s_after = rm_pair(s)
        #짝지어진 문자열 제거 전후가 같으면 : 더이상 제거할 문자 X
        if s == s_after :
        	#문자열이 모두 제거되었을때
            if len(s_after) == 0 :
                return 1
            else :
                return 0
        else :
            s = s_after

 

로직 자체는 맞는데, 시간 초과로 나온다.. 문자열의 길이가 1000000 이하의 자연수라는데, 여기서 문자열이 길면 시간 초과가 뜨는 것 같은데, 어떤 방법을 써야 시간복잡도를 줄일 수 있을까 ?

 

- > s.replace()에서 시간이 매우 많이 들었다고 한다. replace 메소드는 모든 문자열을 돌면서 해당 문자열을 제거하는데, while True문이 계속 반복되게 되면 긴 문자열이 올 경우 이를 계속 반복해야 하기에 , 시간초과가 난 것 같다.

 

정답 풀이(Stack 활용)

def solution(s):
    #stack 활용
    stack = []
    for c in s :
        #stack이 비어있거나, 전 문자와 같을때(짝지어져 있을 때)
        if stack and stack[-1] == c :
            stack.pop()
        else : 
            stack.append(c)
    
    if len(stack) == 0 :
        return 1
    else :
        return 0

 

 

풀이 로직 :

s 문자열을 받아와 문자 하나씩 받아옴

-> stack이 비어있거나 맨 위의 문자가 들어온 문자와 같을시에(짝지어져 있을때) 제거

-> 반복을 마치고 stack의 길이가 0일시에, 모두 제거된 것이므로 1 반환

 

 

Github Link  ←

BackJoon-Programmers/프로그래머스/2/12973. 짝지어 제거하기 at main · jaeheonki/BackJoon-Programmers