문제 설명
전체 코드
from collections import deque
def solution(s):
answer = []
for string in s:
stack = []
count = 0
for i in string:
if i == '0':
if stack[-2:] == ['1','1']:
count += 1
stack.pop()
stack.pop()
else:
stack.append(i)
else:
stack.append(i)
if count == 0:
answer.append(string)
else:
final = deque()
while stack:
if stack[-1] == '1':
final.append(stack.pop())
elif stack[-1] == '0':
break
while count > 0:
final.appendleft('0')
final.appendleft('1')
final.appendleft('1')
count -= 1
while stack:
final.appendleft(stack.pop())
answer.append(''.join(final))
return answer해결 방법
처음에 문제를 보고 아 문자열 상에서 바꾸면 되겠지? 라는 생각으로 for문을 중첩으로 3번 돌렸다가 시간초과로 대참사가 났다. 그리하여 다른 사람의 코드를 참조하였다. 이 문제를 stack과 queue의 관점에서 푸는 것이 신기하였다. 그리고 이게 가장 깔끔한 풀이이다. 먼저 s안에 for문을 사용하여 string으로 원소를 하나 받고 string의 원소를 i로 받은 후 문자열 i가 0일때 미리 선언해 놓은 stack 리스트에 마지막 두 원소가 [1, 1] 이라면 110이라는 값이 존재하는 것이므로 count를 +1 해주고 stack의 마지막 두 원소를 pop해준다. 만약 stack의 마지막 두 원소가 [1, 1] 이 아니라면 110이 아니므로 그냥 stack에 문자열 i를 append 시켜준다. 또한 i가 0이 아니라면 stack에 append 시켜준다.
그 다음 코드를 보면 count가 만약 0일시에 110이라는 문자열이 없다는 것이므로 answer에 string 값을 그대로 append 시켜준다. 그게 아니라면 final 이라는 deque()를 선언해주고
stack을 while로 반복하면 stack의 마지막 원소가 1 이라면 final deque()에 append 시켜주며 stack은 pop을 한다. 그게 아닌 0이 나오면 break를 해준다. 그리고 110을 count만큼 final deque()에 appendleft를 하여 삽입해준다. 마지막으로 stack에 있는 원소들을 appendleft로 final에 삽입해주고 join으로 answer에 결과 값을 넣어준다.
- 정말 쉽지 않은 문제이다. 하지만 문제를 잘만들었다고 생각하며 이런 문제가 나왔을때 stack과 queue를 생각해봐야 겠다고 느꼈다. 꼭 디버깅을 해볼것!!!!
