프로그래머스 110 옮기기 (python, 파이썬)

• 문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

• 제한사항
  • 1 ≤ s의 길이 ≤ 1,000,000
  • 1 ≤ s의 각 원소 길이 ≤ 1,000,000
  • 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

---

• 입/출력

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

---

• 코드

from collections import deque

def solution(s):
    answer = []
    for string in s :
        stack = []
        count = 0
        for s in string:
            
            # 문자열이 0이면
            if s == '0':
                
                # 앞에 2개가 1, 1인지 확인
                if stack[-2:] == ['1', '1']:
                    count += 1
                    stack.pop()
                    stack.pop()
                    
                # 앞에 2개가 1, 1이 아니면 그냥 0을 추가
                else:
                    stack.append(s)
                    
            # 문자열이 0이 아니면 그냥 추가
            else:
                stack.append(s)
        
        # 110이 없기 때문에 변화 불가능
        if count == 0:
            answer.append(string)
        
        # 110이 있다면
        else:
            final = deque()
            
            # 0이 나오기 전까지는 append
            while stack:
                if stack[-1] == '1':
                    final.append(stack.pop())
                elif stack[-1] == '0':
                    break
            
            # 0이 나왔다면 110을 주어진 count만큼 append
            while count > 0:
                final.appendleft('0')
                final.appendleft('1')
                final.appendleft('1')
                count -= 1
            
            # stack에 남아있는거 다 추가
            while stack:
                final.appendleft(stack.pop())
            answer.append(''.join(final))
    
    return answer

110은 서로 겹쳐서 110이 생성될수 없기때문에 모든 110을 뽑아낸다.

이후 뒤에서부터 0이 나오는 순간에 110을 개수만큼 추가시켜준다. 

그외에는 그냥 append를 시켜준다

---

• 출처

https://programmers.co.kr/learn/courses/30/lessons/77886?language=python3