[알고리즘] 프로그래머스 | 짝지어 제거하기 (페어)

짝지어 제거하기

답: 

def solution(s):
    stack = [] 
    for i in s:
        print(stack)
        if not stack:
            stack.append(i)
        elif stack[-1] != i:
            stack.append(i)
        else:    #stack[-1] == i인 경우
            stack.pop()
    return 0 if stack else 1

 

 

문제 분석 및 해석

같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다

이 과정을 반복해 문자열을 모두 제거한다면  1, 아닐 경우 0을 리턴

 

 

>> 풀이생각

짝지어 제거하기에서 올바른괄호가 생각났다

stack을 사용해서 푸는 문제구나!

 

 

>> 페어 풀이 지도 받음

스택에 없으면 스택에 추가(신병 받아라~)

스택에 있으면 스택[-1]과 i를 검증

 

 

 

 

첫 풀이.

 

list로 풀던 string으로 풀던 list out of range 혹은 string out of range 가 난다

 

def solution(s):    
    answer = list(s)    
    len_answer = len(answer) - 1
    i = len_answer
    while len_answer <= 0 or i < 0:
        if s[i] == s[i+1]:
            answer.remove(s[i+1])
            answer.remove(s[i])

 

 

 

 

페어 풀이.

 

말로 설명을 듣고 풀이를 해보았다.

테스트케이스는 잘 통과하는데 제출 시 13번 케이스를 통과하지 못했다.

 

def solution(s):
    stack = [] 
    for i in s:
        if not stack:
            stack.append(i)
        elif stack[-1] == i:
            stack.pop()
    return 0 if stack else 1

 

 

문제점을 생각해보았는데, stack에 아예 요소가 없을 경우에만 stack을 하나 넣는 방식으로 풀이했기 때문이라고 생각했다

elif로 stack요소와 현재 요소를 비교하여 append해주는 부분을 추가!

 

def solution(s):
    stack = [] 
    for i in s:
        if not stack:
            stack.append(i)
        elif stack[-1] != i:
            stack.append(i)
            ...

 

---

 

이후 팀원 풀이를 보면서 문제점을 함께 찾았고, 다른 문제점도 발견했다

완벽히 대칭되는 요소들은 문제없이 풀이되지만

stack에 이미 겹치는 요소가 있을 경우 해당 요소를 무시하고 반복문을 진행하며, 그 과정에서 올바르게 짝지어지는 듯한 현상을 보인다.

입력 : "cabcdebadeedabedbac"  실제 결과값 0 => 코드 결과값 1  

def solution(s):
    stack = [] 
    for i in s:
        print(stack)
        if i not in stack:
            stack.append(i)
        else:
            if stack[-1] == i:
                stack.pop()
    if stack:
        return 0
    return 1

 

 

나의 풀이

이 경우에는 대칭되어 풀이가 된다

 

 

하지만 아래 케이스의 경우는 풀이가 되지 않았다.

 

0이 나와야 하는 반례

1이 나와서 풀이되지 않음!

 

 

 

반례 예시

입력  출력

• "cbaabbbaaccc" 1 # 성공 케이스
• "cabcdebadeedabedcbac" 1 # 성공 케이스
• "cabcdebadeedabedbac" 0 # 실패 케이스, 출력이 1로 처리됨 ▷ c가 하나 빠져있습니다
• "abcbaabbcba" 0 # 실패 케이스, 출력이 1로 처리됨 ▷ b가 하나 더 들어가 있습니다

 

 

 

---

 

리뷰.

stack으로 혼자 끙끙대다 페어프로그래밍 했다!

팀원에게 문제 풀이 힌트를 받아 풀이했고, 프로그래머스 오류도 찾았다!

 

문제점을 찾아 코드를 보완하는 과정이 재밌었다:)

 

 

 

 

+++

return 값으로 boolean값 return하기

 

return int(len(stack) == 0)