프로그래머스 lv3 110옮기기

1. 개요

• https://school.programmers.co.kr/learn/courses/30/lessons/77886

2. 풀이

from collections import deque

def solution(strings):
    return [call(s) for s in strings]
    
def call(s):
    answer, count, remain = deque(), 0, []
    # 가능한 110의 갯수를 모조리 뽑아 낸다.
    for c in s:
        if c=='0' and remain[-2:]==['1','1']:
            remain.pop()
            remain.pop()
            count += 1
        else:
            remain.append(c)
    
    # 110 추출이 불가능하면 고대로 반환한다.
    if count==0:
        return s

    # 어떻게 배치해 사전순으로 가장 앞서게 할수 있을까
    # 0은 되도록 왼쪽에 있어야하고 1은 최대한 오른쪽으로 가야한다.
    # 그렇다면 remain을 오른쪽에서 왼쪽으로 검색해가면서
    # 가장 처음나오는 0 오른쪽에 110을 몰아 붙여버리면 된다.
    # 0을 지나칠때마다 0이 왼쪽으로 이동하여 손해다!
    while remain:
        c = remain.pop()
        if c=='0':
            answer.extendleft(count*['0', '1', '1'])
            answer.appendleft(c)
            count = 0
            break
        else:
            answer.append(c)
    
    while remain:
        answer.appendleft(remain.pop())

    # remain이 죄다 1이면
    # 그냥 앞에 붙여버리는것이 이득이다.
    # 110이니깐 0이 세번째 자리에 위치하기 때문이다.
    answer.extendleft(count*['0', '1', '1'])

    return ''.join(answer)