짝지어 제거하기

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 짝지어 제거하기

풀이)

접근)

처음에는 문제에 나온 예시대로 문자열을 탐색하다가 현재 문자가 다음 문자와 동일하다면 제거하고 새로운 문자열을 만들어 탐색하는 방법을 이용했는데 시간초과가 났다.

두번째 풀이로는 'aa', 'bb', 'cc'를 포함한 문자열을 모두 제거하는 방법을 이용했는데 생각해보니 이 방법을 이용한다면 지우는 순서가 바뀐다.(중간 과정에서 문제가 발생할 수 있다.)

마지막으로 찾은 풀이는 스택을 이용한 방법이고 알고리즘은 다음과 같다.

알고리즘)

문자열을 탐색하면서 스택이 비어있다면 원소를 스택에 push

스택에 원소가 존재했을때

     스택의 top과 원소값이 같다면 스택의 top을 pop

     다르다면 원소를 스택에 push

이 방법을 이용했을 때 모든 문자열을 탐색한 뒤 list에 값이 존재한다면 모든 문자열을 제거하지 못한것이고 list가 비어있다면 모든 문자열을 제거하는데에 성공한것이다.

코드)

import copy
def solution(s):
    answer = -1    
    list1 = []
    for i in s:    
        if len(list1) > 0:
            if list1[len(list1)-1] == i: # 마지막 원소와 같다면
                list1.pop(len(list1) -1)
            else:
                list1.append(i)
        else:
            list1.append(i)   
 
    if len(list1) == 0:
        answer = 1
    else:
        answer = 0
    return answer