[프로그래머스] 짝지어 제거하기 - Lv.2

프로그래머스 12973번 문제인 "짝지어 제거하기" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] 짝지어 제거하기 Lv.2 - [파이썬/python]

 

 

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

---

💻 문제 설명

 

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

 

예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

---

🚨 제한사항

 

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

---

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

 

프로그래머스-짝지어-제거하기-파이썬-코드

 

 

def solution(s):

   

    stack = [] # 스택을 초기화

   

    # 문자열 s의 각 문자에 대해 순회

    for i in s:

       

        # 스택이 비어있지 않고, 스택의 top에 있는 문자와 현재 문자가 같다면

        if stack and stack[-1] == i:

            stack.pop() # 스택에서 pop을 합니다.

            continue  # 다음 문자로 넘어갑니다.

       

        stack.append(i) # 그렇지 않다면 현재 문자를 스택에 push합니다.

    # 모든 문자를 순회한 후에 스택이 비어있다면 짝지어 제거하기가 성공적으로 수행된 것이므로 1을 반환

    # 그렇지 않다면 0을 반환

    return int(not stack)

 

 

---

⏱ 시간복잡도

 

위 코드의 시간 복잡도는 O(n)입니다.

 

문자열 순회하기: for i in s

문자열 s의 각 문자를 순회하는 데 O(n)의 시간이 소요됩니다. 여기서 n은 문자열 s의 길이입니다.

 

스택 조작하기: stack.pop(), stack.append(i)

스택에서 pop과 push를 수행하는 데는 상수 시간, 즉 O(1)의 시간이 소요됩니다. 이러한 연산들은 문자열의 각 문자에 대해 한 번씩 수행되므로, 전체적으로는 O(n)의 시간이 소요됩니다.

 

따라서, 이 코드는 문자열 s를 한 번만 순회하고, 각 문자에 대해 상수 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(n)입니다. 이는 입력 크기에 선형적으로 비례하는 시간 복잡도를 의미합니다.

---

🏳‍🌈 테스트 결과

 

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

 

프로그래머스-짝지어-제거하기-테스트-결과