프로그래머스 짝지어 제거하기 (python, 파이썬)

• 문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

---

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

---

• 입/출력

s	result
baabaa	1
cdcd	0

---

 

• 코드

def solution(s):
    # (1)
    if len(s) % 2 == 1:
        return 0
    
    left = 0
    right = 1
    temp = []
    
    while right < len(s):
    
    	# (2)
        l = s[left]
        r = s[right]
        
        # (3)
        if l != r:
            # (3)-1
            temp.append(left)
            left = right
            right = right + 1
            
        # (4)
        else:
        
            # (4)-1
            if temp:
                left = temp.pop()
                right = right + 1
                
            # (4)-2
            else:
                left = right + 1
                right = right + 2
        
    return 0 if temp else 1

이중포인터를 사용해서 문제를 풀었다.

(1) : 먼저 길이가 홀수인 경우는 문자열을 무조건 다 제거할 수 없기 때문에 0을 return한다.

 

(2) : 여기부터는 길이가 모두 짝수인 경우이다. left에 0 / right에 1을 담아주고 포인터를 옮겨가면서 확인한다

 

(3) : 만약 left의 값과 right의 값이 같아서 지우지 못하는 경우

(3) - 1 : left의 값을 temp list에 잠시 담아둔다. 그리고 포인터는 하나씩 오른쪽으로 이동하면서 다음 값을 확인하게 만들어준다

 

(4) : 만약 left의 값과 right의 값이 같아서 지울수 있는 경우

(4) - 1 : temp의 값이 남아있으면 앞에서부터 먼저 지워줘야하기 때문에 temp의 값을 pop해서 left에 담아주고 right는 한칸 증가시킨다.

(4) - 2 : temp의 값이 없다면 앞에서 다 지워지고 있다는 말이기 때문에 right를 기준으로 다음 2개를 이어서 확인해주면 된다.

---ex) 'baabaa'을 예시로 순서대로 값을 확인하면서 이해보시면 편할거에요!

left	left_word	right	right_word	temp
0	'b'	1	'a'	[]
1	'a'	2	'a'	[0]
0	'b'	3	'b'	[]
4	'a'	5	'a'	[]
6	x	7	x	[]

 right의 값이 본 문자열의 길이보다 크면 while문 종료!

 

temp에 값이 남아있지 않다면 다 제거가 되었으니 1을 return하고 남아있다면 다 제거를 못한것이기 때문에 0을 return

---

• 출처

programmers.co.kr/learn/courses/30/lessons/12973?language=python3