[Python] 프로그래머스, 짝지어 제거하기 Lv.2 (feat.stack, 시간초과, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

 

짝지어 제거하기

문제 링크

프로그래머스

 

 

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞 뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다.

 

문자열 's'가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

 

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

 

 

제한 조건

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

 

 

입출력 예

s	result
baabaa	1
cdcd	0

 

 

입출력 예 설명

입출력 예#1

위의 예시와 같습니다.

 

입출력 예#2

문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

 

 

 

해결 과정

 

1. stack 문제로 접근하여 선언을 해주었고 문자열 's'만큼 for loop을 돌려줍니다.

 

2. stack이 비어있다면 비교를 위해 i번째 문자열을 append 해줍니다.

 

3. stack에 담긴 마지막 값과 i번째 문자열이 같다면  stack에 담긴 마지막 값을 제거해 줍니다.

 

4. 3번의 조건이 충족되지 않고 다르다면 i번째 문자열을 stack에 추가로 append 해줍니다.

 

5. 모두 제거되지 않고 stack에 문자열이 남아있다면 0을 반환, 짝이 맞아 모두 제거되었다면 1을 반환합니다.

 

💡 Point. Stack을 활용하여 접근하기

def solution(s):
    stack = []
    
    for i in range(len(s)):
        if not stack:               # stack이 비어있다면
            stack.append(s[i])      # 'i번째 문자열' append
        else:
            if stack[-1] == s[i]:   # 'stack 마지막 값'과 'i번째 문자열'이 같다면
                stack.pop()         # 'stack 마지막 값' 제거
            else:
                stack.append(s[i])  # 다르다면 'i번째 문자열' append
    
    return 0 if stack else 1        # stack이 남아있으면 0 모두 제거되었으면 1 반환

 

 

stack의 개념을 활용한다면 실행 결과 테스트 케이스와 효율성 테스트 모두 통과하는 걸 볼 수 있습니다.

 

 

 

또 다른 풀이

def solution(s):
    index = 0
    while index >= 0 and index < len(s) - 1:
        index += 1
        if s[index - 1] == s[index]:
            s = s[:index - 1] + s[index + 1:]
            index = 0

    return 0 if len(s) else 1

 

 

위 코드는 while문을 활용하여 index를 카운트해서 앞과 뒤 문자열을 비교해 가며 제거하는 코드입니다. 제거되었을 땐 index를 0으로 초기화하여 반복 작업하는 방식인데 문자열의 길이가 1,000,000 이하이기 때문에 너무 큰 값이 들어온다면 시간 초과 문제가 발생하게 됩니다.

 

 

 

 

 

 

---

 

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges