[Lv2] 짝지어 제거하기(python)

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/12973?language=python3 

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

 

 

2. 풀이 과정

- stack을 사용해서 stack의 top 문자와 s[i]가 같으면 stack.pop()하고 아니면 stack.append()를 해가다가 최종 stack이 빈 stack이면 1을 리턴.

 

- "붙어있어야 한다 + 붙어있는게 사라졌을 때, 새로운 짝이 생긴다 (b aa b -> bb) "

-> aa가 사리지고 나서 새로운 쌍을 확인하기 위해선 사라진 문자의 직전 문자를 봐야 한다. 

-> 쌍을 이루지 않는 직전 문자들을 계속 순서대로 기억해야 함

-> stack을 사용한다.의 과정으로 stack을 사용한 풀이라는 걸 유추하기!

 

 

3. 실수한 내용 & 새로 안 내용

- list를 사용한 stack에는 top(), size()대신 각각 stack[-], len(stack)을 사용할 것

- for문 돌릴 때 매번 stack.empty()를 하기 번거로울 땐 stack 선언 시 사용되지 않는 대상 (위 문제에선 대문자 알파벳)을 하나 넣어두면 stack.empty()확인 안해도 됨!

 

4. 코드

# 입력 범위가 100만이므로 nlogn으로 풀어야 함
def solution(s):
    answer = -1   
    stack = ["A"]
    
    for x in s:
        if stack[-1] == x:
            stack.pop()
        else:
            stack.append(x)
    
    if len(stack) == 1:
        return 1
    else:
        return 0
    return answer