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

접근

---

처음에 시간초과가 날 로직밖에 생각이 안났다.

문자열을 한 바퀴만 돌린다고 해도 100M이다. 

O(N log N)일 경우, 딱 마지노선이라 생각했기 때문에 무조건 O(N)으로 끝내야겠다고 생각했다. 

 

문자열에서 조건이 맞으면 문자들을 제거해야 하기 때문에 빠르게 배열의 중간 원소를 제거할 수 있는 알고리즘과 자료구조가 무엇인지를 생각했다.

 

• 배열의 원소를 빠르게 제거해야 하는 경우 → 스택 활용

 

로직

---

• 문자열의 원소에 대해 반복문을 돌린다.
• 각 문자들을 스택에 저장한다.
• 스택의 마지막 문자와 현재 문자가 동일할 경우, 스택의 마지막 문자를 제거한다 → O(1)
• 반복문이 종료된 이후, 스택에 문자가 남아있는 경우 성공적으로 수행하지 못한 것. 반대로 빈 스택일 경우 성공적으로 수행할 수 있음을 의미한다.

 

코드

---

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

    if len(stack) == 0:
        return 1
    else :
        return 0