문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

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

b aa baa → bb aa → aa →

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

제한사항

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

입출력 예

s	result
baabaa	1
cdcd	0

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

접근방법

처음에는 문자열을 처음부터 확인하며 현재 인덱스와 다음 인덱스가 같을 때 문자를 제거하고 다시 처음부터 확인하며 문자열을 제거하도록 구현하였다. 원하는 값은 나왔지만 시간초과되는 테스트 케이스가 많았다.

다시 생각한 방법은 새로운 배열을 만들고, 배열의 마지막 인덱스에 해당하는 문자와 문자열에서 확인하고 있는 현재 인덱스의 값이 같으면 배열을 pop해주고, 다르다면 append해주는 방식으로 구현하였고 시간 내에 해결되는 것을 확인할 수 있었다.

• 빈 배열 result를 선언한다.
• 문자열 s의 길이만큼 i에 대한 for문을 돌린다.
  -> result가 비어있다면 s[i]를 append한다.
  -> result가 비어있지않고, result의 마지막 원소와 s[i]가 같다면 result의 마지막 원소를 pop한다.
  -> result가 비어있지않고, result의 마지막 원소와 s[i]가 다르다면 result에 s[i]를 append한다.
• 만약 result가 비어있다면 answer를 1로 갱신하고, 비어있지 않다면 0으로 갱신한다.
• result로 return한다.

solution.py

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