[프로그래머스][python] 짝지어 제거하기 - stack/queue

문제

• 프로그래머스 짝지어 제거하기
• Level 2
• Link

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

 

나의 접근

첫 시도 (시간 초과)

정확도는 테스트 케이스를 모두 패스했으나 효율성에서 단 한개의 테스트 케이스도 통과하지 못했다.. 문자열을 리스트로 받고 큐의 상위 원소가 들어오는 원소와 같으면 기존의 큐에서 pop해주고, 그러지 않은 경우에는 q에 추가를 해주었다.

아무래도 문자열이 엄청 길어지는 테스트 케이스에서 효율성을 패스를 못하는 것 같았다.

def solution(s):
    q = []
    wordlst = list(s)
    
    while len(wordlst) > 0:
        letter = wordlst.pop(0)
        if not q:
            q.append(letter)
            
        elif q[-1] == letter:
            q.pop(-1)
            
        else:
            q.append(letter)
            
    if len(q) != 0:
        return 0
    else:
        return 1
    

 

두번째 시도 (패스)

생각해보니 구욷이 문자열을 리스트로 parse하고 그 리스트에서 문자열들을 제거해줄 필요가 없다. 그 부분을 생략해서 코드를 작성해보니 효율성이 바로 패스 됐다. 간단!

def solution(s):
    q = []
    idx = 0
    while idx < len(s):
        letter = s[idx]
        if not q:
            q.append(letter)
        elif q[-1] == letter:
            q.pop()
        else:
            q.append(letter)
        idx += 1
            
    if q:
        return 0
    else:
        return 1