[Programmers] 12973.py 짝지어 제거하기

먼저 문제 그대로 풀었으나 역시나 시간초과로 실패.

사실 문제 그대로 풀기는 테스트를 통과해야겠다는 마음보다 어떤 식으로 접근하면 풀리겠구나, 하는 찔러보기 느낌.

 

def solution(s):
    index = 1
    arr = list(s)

    while True:
        if index >= len(arr):
            break

        if arr[index-1] == arr[index]:
            arr.pop(index)
            arr.pop(index-1)
            index = 1 if index - 1 <= 1 else index -1
        else:
            index += 1

    if len(arr) == 0:
        return int(True)
    else:
        return int(False)

 

 

별도의 빈 list를 만들어서 상쇄되지 않는 값을 옮겨 담아 비교하는 방식을 생각했지만 위 풀이 방식과 연산속도가 크게 다르지 않을 것이라고 판단하여 시도하지 않았다.

 

위 방식에서 가장 시간이 많이 소요되는 부분이 아무래도 .pop method라고 생각해서 이를 쓰지 않는 방식을 고민했는데 딱히 pop보다 빠른 속도를 낼 수 있을거라 기대되는 방식이 떠오르지 않아 고민하다가 결국 다른 분들의 조언글을 보았는데 "stack을 사용하여 해결할 수 있다." 라는 글을 보고 처음 생각했던 방식을 구현해보았다.

 

def solution(s):

    arr = [s[0]]
    s = s[1:]
    
    for c in s:
        if len(arr) > 0 and c  == arr[-1]:
            arr.pop()
        else:
            arr.append(c)

    if arr:
        return 0
    else:
        return 1

 

그렇게 위 코드로 해결.

그동안의 경험으로 연산 횟수를 줄이려면 method 사용을 줄이는 편이 좋다. 라고 생각했는데 그것만이 답은 아니었다.

일단 떠오르는 다른 방식이 있다면 시도해보고 더 많이 겪어보자.

 

---

마지막으로 다른 사람의 풀이에서 __eq__ method를 오버로딩하여 사용하는 방식을 만났다.

js 내장 함수 공부할 때 이를 오버로딩할 수 있다는 사실을 알고 있었지만 실제로 사용하는 방식을 보니 반가웠다.