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

30 Aug 2021

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

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12973
난이도: Level 2

풀이(시간초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#시간초과
def solution(s):
    i = -1

    while True:
        i += 1
        if i == len(s) - 2:
            break
        elif s[i] == s[i + 1]:
            s = s[:i] + s[i + 2:]
            i = -1
            if len(s) == 2:
                return 1

    return 0

문자열 slice를 이용하여 구현하였을 때 반복문 횟수의 증가로 효율성 테스트에서 시간초과 문제가 발생했다.

풀이(시간초과 해결)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(s):
    stack = []

    for i in range(len(s)):
        if len(stack) == 0:
            stack.append(s[i])
        elif s[i] == stack[-1]:
            stack.pop()
        else:
            stack.append(s[i])

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

💡 stack 구조 활용

알파벳의 짝을 찾은 경우 pop()으로 제거&아닌 경우 append()로 넣는 과정 반복
마지막에 stack의 길이가 0인 경우 ➔ 짝지어 제거하기 성공적으로 수행 가능

algorithms