[Lv2.] 짝지어 제거하기

👉 사용 언어 : PYTHON3

 

✅ Solution

def solution(s):
    s = list(s)
    i = 0
    while i < len(s)-1:
        if s[i] == s[i+1]:
            del s[i:i+2]
            if i > 0:
                i -= 1
        else:
            i += 1
    return int(len(s) == 0)

 

👉 정확성 테스트는 통과 BUT 효율성 테스트에서 시간 초과 발생

( 문자열 s길이가 최대 1,000,000이므로 )

from collections import deque
def solution(s):
    s = deque(s)
    temp = deque([])
    for i in s.copy():
        if len(temp) > 0 and temp[len(temp)-1] == i:
            temp.pop()
            s.popleft()
        else:
            temp.append(s.popleft())
    return int(len(temp) < 1)

 

👉 문제 설명 및 제한 사항

• 매개변수 : 알파벳 소문자로 이루어진 문자열
  • 1,000,000이하의 자연수
• 리턴값 : 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환
  • 성공적으로 수행할 수 있으면 1
  • 아닐 경우 0
• 예시
  • S = baabaa
  • b aa baa → bb aa → aa →
  • 모두 제거할 수 있으므로 1을 반환한다.

👉 아이디어

• 문자열 s를 순회하며 2개씩 지워나가면 순회 + 문자열 슬라이싱을 사용하기 때문에 O(b-a) + O(len(s))로 비효율적이다.
• 따라서 시간복잡도가 O(1)인 pop() 연산과 append() 연산을 사용하여 풀이한다.
• 더 효율적인 연산을 위해 deque를 사용하여 풀이한다.
• 기본적인 아이디어
  • temp 배열을 하나 생성한 후, s의 첫 문자와 temp 배열의 마지막 문자가 같은 경우에 두 개를 pop한다.
    • 오른쪽 끝 : pop()
    • 왼쪽 끝 : popleft()
  • 다른 경우에는 s의 첫 문자를 pop하여 temp 배열에 추가한다.
  • temp 배열의 길이가 0인지❓ 아닌지❓ 를 반환한다.
    • true/false > 1/0으로 변환해서❗️

 

✅ 다른 사람 풀이 참고

def solution(s):
    answer = []
    for i in s:
        if not(answer):
            answer.append(i)
        else:
            if(answer[-1] == i):
                answer.pop()
            else:
                answer.append(i)    
    return not(answer)

 

👉 깨달은 것 / 알게된 것

• s의 원소를 변경하지 않고 풀이할 수 있다.
  • s를 순회하며 원소를 하나씩 뽑아 answer의 맨 끝 원소와 비교하고, 같을 경우 answer에서만 pop 연산을 수행하면 된다.
• deque를 사용하지 않고도 풀이할 수 있다.
• not 연산은 1/0 값을 리턴 하므로 변환하지 않아도 된다.
• 파이썬에서 deque를 사용할 때는 반복 중에 deque를 수정하지 않도록 주의해야 한다.
  • deque를 복사 하여 반복
  • 반복 중에 수정하지 않 도록 수정