포스트

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

게시 업데이트
By sinyeowon
읽는 시간 2분
For the English version of this post, see here.
[Python] 프로그래머스 - 짝지어 제거하기

Programmers 짝지어 제거하기

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def solution(s):

    stack = []

    for ch in s:

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

            stack.pop()

        else:

            stack.append(ch)

    return 1 if not stack else 0
  • stack에 알파벳 하나를 넣고, 다음 알파벳을 들고와서 전에 넣은 알파벳과 일치하면 전에 넣은 알파벳을 pop하고, 일치하지 않으면 해당 알파벳도 stack에 넣는 방식
    • 이렇게 하다보면, 모든 알파벳을 대입했을때 짝지어 제거하기에 성공한다면 stack은 비어있어야함
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def solution(s):
    answer = -1
    arr = []

    while True:
        if len(arr) == len(s):
            return 1
        cnt = 1
        for i in range(0, len(s)-1):
            if s[i] == s[i+1]:
                arr.append(s[i])
                arr.append(s[i+1])
                if i+2 > len(s)-1 and i==0:
                    return 1
                elif i+2 > len(s)-1:
                    s = s[:i]
                elif i == 0:
                    s = s[i+2:]
                else:
                    s = s[:i] + s[i+2:]
                break
            else:
                cnt += 1
                if cnt == len(s):
                    return 0

    return answer

처음에는 위와 같이 풀었다가 정확성 테스트에서는 시간 초과, 효율성 테스트는 실패했음

위 문제는 스택을 사용해서 풀어야 함

  • 스택을 사용해야 한다는 사실은 알았지만 어떻게 활용하면 좋을지 고민하다가 스택을 사용하지 못한 풀이였음

  • 그냥 다른 배열을 새로 만들어서 푼 것과 마찬가지

Programmers, Python
Python programmers