문제 풀때 주의사항 (프로그래머스 - 짝지어 제거하기 with Python)

그냥 무작정 풀지않기

 

-> 이 문제가 어떤 자료구조, 알고리즘을 사용해야하는지 유심히 볼 필요가 있음.

programmers.co.kr/learn/courses/30/lessons/12973

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

 

문제가 쉽다 생각해서 그냥 간단히 풀려했음

def solution(s):
    s=list(s)
    
    while s: # 다 비거나 찌꺼기 남을때까지
        k=len(s)
        for index,(i,j) in enumerate(zip(s,s[1:])):
            if i==j:
                k=index
        if k==len(s):
            return 0
        s=s[:k]+s[k+2:]
        
    return 1

 

 

답은 잘 찾는거같은데 시간초과

그래서 어떻게 할지 생각하던중 문제가 스택을 쓰면 어처구니 없이 쉽고 시간복잡도가 O(n) 으로 줄어드는걸 확인

 

정답코드:

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

    return answer

 

앞으론 무작정 풀려고만 하지말기