[프로그래머스 Level 2] 짝지어 제거하기 (Python 파이썬) 풀이 방법

평일 오전 8시에 뚝섬유원지(본가) ~ 상도(자취방)까지 지하철을 탄 건 처음이었는데, 사람이 열차에 꽉 차서 놀랐다. 다행히 내리는 분이 계셔서 그 자리에 탔지만 겨울철 패딩을 입고 다른 사람들과 부대끼는게 썩 좋은 느낌은 아니었다. 장점이 하나 있다면 청담역까지 한강을 가장 가까이서 보며 건넜다는 점?

 

아침에 일어나 거실에서 조용히 동트기전의 한강을 바라보면 기분이 참 좋다. 올림픽대로랑 강변대로를 바쁘게 달리는 차들을 보며 오늘도 열심히 살아야겠다는 다짐을 한 번 더 할 수 있다.

 

 

 

프로그래머스 <짝지어 제거하기> 문제 보기

https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

 

프로그래머스 <짝지어 제거하기> 문제 풀이

def solution(s):
    if len(s) == 0:
        return 1
    if len(s) == 1:
        return 0
    stack = []
    stack.append(s[0])
    for i in range(1, len(s)):
        if len(stack) == 0:
            stack.append(s[i])
        elif s[i] == stack[-1]:
            stack.pop()
        else:
            stack.append(s[i])
    if len(stack) == 0:
        return 1
    return 0

이 문제의 포인트는 stack을 활용함으로써 시간복잡도를 n으로 만들어주는 것이었다. 문자열 s의 한 자리씩 stack에 값을 넣어가며, stack의 가장 마지막 값과 s의 현재값을 비교했을 때 같다면 stack에서 pop을 해주고 다르다면 append 해주는 방식이다.

 

 

첫 번째 도전

def solution(s):
    answer = 0
    i = 0
    
    while i < len(s)-1:
        if s[i] == s[i+1]:
            s = s[:i]+s[i+2:]
            i = -1
        i += 1
        if len(s) == 0:
            return 1

    return answer

처음에는 while문 안에서 if로 조건을 체크해 문자열을 잘라 더해주는 방식을 선택했다. 시간복잡도가 n^2가 되며 시간 초과로 인한 실패가 떴다.

 

두 번째 도전

def solution(s):
    answer = 0
    i = 0
    
    while i < len(s)-1:
        if s[i] == s[i+1]:
            s = s[:i]+s[i+2:]
            i = -1
        i += 1
        if len(s) == 0:
            return 1
        if i >= len(s)-1:
            return answer

혹시나 return을 while 안에 넣어주면 다른 부분이 있을까 싶어 도전해봤지만 결과는 역시나 시간 초과

입력 범위가 100만이기 때문에 시간복잡도는 n 혹은 nlogn으로 풀어주는 것이 마땅하다.

 

 

 

다른 풀이

def solution(s):
    stack = []
    for i in s:
        if len(stack) == 0:
            stack.append(i)
        elif stack[-1] == i:
            stack.pop()
        else:
            stack.append(i)
    if len(stack) == 0:
        return 1
    else:
        return 0

나와 풀이방법은 같지만 훨씬 간단하다. 나는 필요없는 경우의 수를 너무 많이 체크해주었다. stack이 비어 있으면 넣어주고, 비어 있지 않을 경우에는 마지막 값이 같다면 pop 해주고 아닐 경우에는 append 해주기만 하면 된다. 이번 문제에서는 시간복잡도에 너무 치중하다보니 코드를 깔끔하게 구현하지 못한 것 같다.

 

하루가 참 짧다. 이러다 두 달이 훅 지나가 4학년이 될까 두렵다.