level2.
짝지어 제거하기
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
while문과 for문을 이용한 풀이 방식 >> 문자열이 길어지면 시간초과
def solution(s):
answer = -1
//짝지어진 문자열을 모두 제거할때 까지 무한 루프
while True:
equal = ''
//짝지어진 문자열 찾아내는 for문
for index,data in enumerate(s):
if index != 0 and data == s[index-1]:
equal = data * 2
break
//만약 짝지어진 문자열이 없다면 while문을 끝낸다
if equal == '':
break
//찾아낸 문자열을 제거한다.
//replace를 사용했지만 다른 방법도 생각!!
s = s.replace(equal,'')
//남은 문자열이 null이면 0 아니면 1
if s != '':
answer = 0
else:
answer = 1
return answer
deque를 이용해서 해결
from collections import deque
def solution(s):
answer = -1
//s를 deque로 설정
ds = deque(s)
//stack
arr = []
//첫번째 값
t1 = ds.popleft()
arr.append(t1)
// 큐가 null될때까지 반복
while ds:
//큐에서 한개씩 뺀다
tmp = ds.popleft()
// 스택에 아무것도 없다면 비교값을 한개 넣어준다.
if arr == []:
arr.append(tmp)
// 비교값이 동일하다면 스택에서 pop하여 제거
elif arr[-1] == tmp:
arr.pop()
//동일하지 않다면 큐값을 스택에 넣어준다.
else:
arr.append(tmp)
// 스택에 남은 값이 있으면 0 없으면 1
if arr == []:
answer = 1
else:
answer = 0
return answer
효율성을 따지자면 스택,큐가 필요했지만 for, while을 이용한 풀이도 공부할수 있었던 문제였다.