[프로그래머스/Python] 짝지어 제거하기

문제

프로그래머스 - 짝지어 제거하기

해결 과정

• 먼저 문자열의 길이가 홀수일 때는 무조건 모두 제거할 수 없으므로 return 0
• stack을 이용해서 문자열을 비교하는데
  • 가장 먼저 stack에 문자열의 첫번째 값을 넣는다.
  • stack의 가장 마지막 값과 같으면 그 마지막 값 pop
  • 다르면 append
• stack의 길이가 0이라면 짝지어서 사라진거고 return 1
  0이 아니라면 짝이 없어서 남아있는 것 return 0

시행착오

• 테스트 결과는 맞는데 다른 테스트 케이스는 시간 초과 및 실패^^,, 그렇게 비효율적인가 네.. 제가 봐도 코드가 좀..

def solution(s):
    origin = s
    new_s = s
    while True:
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                new_s = s[:i] + s[i+2:]
                break
        s = new_s
        if len(new_s) == 0:
            answer = 1
            break
        elif origin == s:
            answer = 0
            break
        
    return answer

• 문자열 자체를 변경하면서 사용하는 것은 문자열이 크면 무리인것같음
• 리스트에 값을 삽입, 삭제 하는 것이 리스트의 크기가 크면 부담스러운 모양이다. 스택을 이용하라
• if stack[-1] == i and len(stack) > 0: 이거랑 if len(stack) > 0 and stack[-1] == i: 이거는 다른 것이다... and도 순서가 중요하다

풀이

def solution(s):
    # 문자열의 길이가 홀수일 때는 0
    if len(s) % 2 != 0: 
        return 0
    
    stack = [s[0]]
    for i in s[1:]:
        # stack에 아무것도 없으면 인덱스 에러가 뜬다. 조건으로 넣어주자
        if len(stack) > 0 and stack[-1] == i:
            stack.pop()
        else:
            stack.append(i)
    return 1 if len(stack) == 0 else 0