짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa
라면
b aa baa
→ bb aa
→ aa
→
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
s result
baabaa 1
cdcd 0
입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.
처음에는 문자열을 처음부터 확인하며 현재 인덱스와 다음 인덱스가 같을 때 문자를 제거하고 다시 처음부터 확인하며 문자열을 제거하도록 구현하였다. 원하는 값은 나왔지만 시간초과되는 테스트 케이스가 많았다.
다시 생각한 방법은 새로운 배열을 만들고, 배열의 마지막 인덱스에 해당하는 문자와 문자열에서 확인하고 있는 현재 인덱스의 값이 같으면 배열을 pop해주고, 다르다면 append해주는 방식으로 구현하였고 시간 내에 해결되는 것을 확인할 수 있었다.
def solution(s):
answer = -1
result = []
for i in range(len(s)):
if len(result)==0:
result.append(s[i])
else:
if result[len(result)-1]==s[i]:
result.pop()
else:
result.append(s[i])
if len(result)==0:
answer=1
else:
answer=0
return answer