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

문제

짝지어 제거하기는

1. 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾는다.

2. 그 둘을 제거하고 문자열을 이어 붙인다.

위 과정을 반복하는 것을 말한다.

 

짝지어 제거하기를 반복하여 문자열을 모두 제거하면 짝지어 제거하기가 종료된다.

문자열 s가 주어졌을 때 짝지어 제거하기를 성공적으로 수행할 수 있는지를 반환하는 함수를 만들어야 한다.

 

 

제한조건

1. 문자열의 길이 : 1,000,000 이하의 자연수

2. 문자열은 모두 소문자로 이루어져 있다.

 

 

코드

def solution(s):
    stack = []
    for character in s:
        if len(stack) == 0:
            stack.append(character)
        else:
            if stack[-1] == character:
                stack.pop()
            else:
                stack.append(character)

    return 1 if len(stack) == 0 else 0

 

 

설명

stack = []

스택을 활용해서 문제를 푼다.

문자열 s의 문자를 스택에 넣으면서

다음에 들어올 문자가 스택에 먼저 쌓여있는 문자와 같다면 스택을 pop한다.

그렇지 않다면 스택에 추가한다.

 

이 과정을 문자열이 가진 문자 개수 만큼 반복한다.

반복이 끝나고 스택에 아무것도 없다면 짝지어 제거하기가 가능한 것이므로 1을 반환하고

그렇지 않다면 짝지어 제거하기가 불가능한 것이므로 0을 반환한다.

 

for character in s:

문자열 s의 문자를 하나씩 꺼내어 반복한다.

 

 

if len(stack) == 0:
	stack.append(character)

스택에 아무것도 들어있지 않은 상태라면

character를 스택에 넣는다.

 

else:
	if stack[-1] == character:
		stack.pop()
	else:
		stack.append(character)

스택에 무언가 들어있다면 아래 조건을 검사한다.

스택에 가장 마지막에 쌓인 문자가 character와 같다면 pop 시킨다.

그렇지 않다면 스택에 character를 넣는다.

 

return 1 if len(stack) == 0 else 0

반복문이 끝나면 스택의 길이를 확인해서 0이면 1을, 그렇지 않으면 0을 반환한다.