[세무민의 코딩일기] 프로그래머스 짝지어 제거하기 문제 풀이

이번 포스팅에서 다룰 문제는 2017년도 팁스타운에서 제공 된 짝지어 제거하기 문제입니다.

이 문제를 풀면서 시간복잡도와 deque의 사용의 장점을 알 수 있었습니다.

---

1. 문제설명

---

2. 입출력 예 설명

---

3. 문제 풀이

이번 문제는 처음에 구상했던 방법은 같은 값이 나오는 i, i+1값을 제거해주면 됩니다. 

이 때 방법의 차이로 시간복잡도 문제에 봉착할 수 있습니다.

제가 처음 생각했던 것은 s = s[:count]+s[count+2:]와 같이 같은 문자가 연속으로 존재한다면 해당 값을 제거하고 

다시 새로운 문자열로 만들어줬습니다.

이 방법을 이용했더니 시간복잡도에 초과가 되었고 곰곰히 생각한 끝에 deque를 생각했습니다.

말 그대로 deque과 반복문을 이용해서 연속으로 들어있는 값이 있다면 deque.pop()을 이용해서 삭제해주면 순서대로 

삭제 및 조합이 될 수 있고 만약 해당 deq값이 비어있다면? 전체 조합이 잘 맞은것이고 비어있지 않는다면 조합이 안된

것입니다.

# 프로그래머스 제출 코드
from collections import deque

def solution(s):
    answer = -1
    deq = deque()

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


    if (len(deq) == 0):
        answer =  1
    else:
        answer =  0
        
    return answer

프로그래머스에 제출한 코드는 위와 같습니다.

---

4. 결과

정답 표시가 되었습니다.

이번 포스팅에서 알 수 있었던 건 시간복잡도에서 deque을 쓰는 것이 문자열을 쪼개는 것보다 좋다는 것이였습니다.

다음에도 유익한 포스팅으로 찾아오겠습니다.