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

https://programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스

문자열 파싱으로 작업하면, 1,000,000이라는 문자열 길이 때문에 시간초과가 나는 문제.

stack 자료구조로 문자열의 앞에서부터 값을 집어넣고, 남은 문자열의 맨 앞단과 스택의 가장 윗값을 비교하면 해결할 수 있다.

deque 라이브러리로 popleft를 활용했는데, 일반 리스트를 활용한 것보다 처리속도가 빠르다.

 

 

	from collections import deque
	def solution(s):
	s = deque(list(s))
	stack = []
	stack.append(s.popleft())
	while s:
	# stack이 비었으면 삽입
	if len(stack) == 0:
	stack.append(s.popleft())
	# 스택 맨 앞값과 남은 string의 맨 앞 비교.
	# 같을 경우 stack과 s에서 둘 다 제거한다.
	elif stack[-1] == s[0]:
	stack.pop()
	s.popleft()
	else:
	# 값이 다르면, stack에 다음 string의 맨 앞 값을 넣는다.
	stack.append(s.popleft())
	# stack에 값이 남아 있으면 짝지어 제거하기 실패한 것.
	if len(stack) != 0:
	return 0
	else:
	return 1

view raw [프로그래머스] 짝지어 제거하기.py hosted with ❤ by GitHub