[Programmers] 2017 팁스타운 > 짝지어 제거하기

문제. 2017 팁스타운 > 짝지어 제거하기

---

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 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을 반환합니다.

 

출처 : 프로그래머스 2017 팁스타운 짝지어 제거하기

코딩테스트 연습 - 짝지어 제거하기

---

나의 풀이

#[Programmers] 2017 팁스타운 > 짝지어 제거하기
def solution(s):
    ls = list(s)
    # 스택을 이용해야 시간적 문제 해결 가능
    stack = []
    for i in ls:
        if len(stack)==0 #동일 의미 not(stack):
            stack.append(i)
        elif stack[-1] == i:
            stack.pop()
        else:
            stack.append(i)
    # stack에 값이 있다면 0을 반환 아니면 1을 반환
    if len(stack): return 0
    else: return 1

처음 문제를 봤을 때, while문을 사용하여 계속 for문을 돌려서 짝을 제거해야 하나 생각했습니다. 곰곰히 생각해보니 그러면 또 시간초과로 문제 해결에 실패할 것 같아 그동안 자주 사용했던 스택이 떠올랐습니다. 스택은 LIFO(Last-In-First-Out)의 자료구조로 가장 나중에 들려온 자료 (stack[-1] in Python)가 가장 먼저 처리(stack.pop() in Python)됩니다.

문제에 적용해보면 먼저 stack에 값이 없을 경우, stack에 값을 넣어주고 그 후, stack에 마지막으로 넣은 값이 해당 순서의 문자값과 동일하다면 제거해주고 아닐 경우에는 다시 또 stack에 쌓아줍니다. 이 작업을 문자열 마지막까지 반복했을 때, 스택에 값이 존재한다면 짝이 지어지지 않았을 경우이므로 문제에서 요구한 대로 0을 반환해주고 스택에 값이 존재하지 않다면 1을 반환해줍니다.

 

다른 사람의 풀이

def solution(s):
    stack = []
    for i in s:
        stack.append(i)
        while True:
            try:
                if stack[-1] == stack[-2]:
                    stack.pop()
                    stack.pop()
                else:
                    break
            except:
                break
    return not stack

처음에 제가 생각했던 구상과 비슷해서 가져와봤습니다. stack[-1] == stack[-2]를 조건으로 pop해주는 부분은 생각하지를 못했는데 몰랐던 부분을 배울 수 있었습니다.