프로그래머스 12973 - 짝지어 제거하기

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

프로그래머스

1. 문제

문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾아서 둘을 제거한뒤 앞뒤로 문자열을 이어붙인다.

짝지어 제거할 수 있으면 1 아니면 0을 리턴한다.

 

2. 문제풀이 포인트

1. 문자열 길이가 1,000,000 이하의 자연수다 시간복잡도를 생각해야한다.

2. 스택으로 푸는 것이 효율적이다.

 

3. 첫번째 풀이(실패사례)

def solution(s):
    while len(s) > 1: 
        s = list(s) #문자열을 리스트로 변환
        for i in range(len(s)-1):
            if s[i] == s[i+1]: s[i] = s[i+1] = '' #인접한 문자가 같은지 검사하고 같다면 빈문자열로 대체
            
        new_s = ''.join(s) #리스트를 다시 문자열로 변환
        if len(s) == len(new_s): break #더이상 제거할 문자가 없다면 종료
        s=new_s
    return 1 if len(s) == 0 else 0

각 단계마다 문자열을 리스트로 변환하고, 중복 검사를 수행하고, 다시 문자열로 조합하는 과정이 반복되므로, 실질적인 처리 시간은 O(n2)에 가깝다.

 

스택을 사용하면 문자열을 한 번만 순회하면서 중복 문자를 제거할 수 있기때문에 O(n)의 시간복잡도를 가진다.

다음은 스택을 사용한 코드다.

 

4. 두번째 풀이(성공사례) : 스택 사용

def solution(s):
    stack = [] #스택
    answer = 0
    for case in s:
        if stack and stack[-1] == case: 
            stack.pop()
        else:
            stack.append(case) 
    if stack: answer = 0
    else: answer = 1
    return answer