[프로그래머스 / 파이썬(Python)] 110 옮기기

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

코딩테스트 연습 - 110 옮기기

 

사전 순으로 앞에 오기 위해서는 "110이 무조건 111보다 앞에 있어야 한다"는 아이디어를 떠올려야 하는 문제입니다.

 

스택을 이용해 문자열을 순회하면서 110을 따로 추출해주고 나면, 110이 모두 제거된 후에 문자열은 연속된 1이 나타나는 지점이 없거나, 한 곳밖에 존재할 수 없습니다. 1이 연속되다가 0이 나타나면 110형태가 되어버리기 때문이죠.

 

따라서 110을 제거한 문자열을 뒤에서부터 순회하면서 1의 개수를 세주고(count_1) stack[:len(stack) - count_1] 위치 뒤에 110 문자열들을 이어 붙여주고, 연속된 1을 붙여주면 됩니다.

 

[풀이]

# 110 다 추출하고 111앞에 넣기
def solution(s):
    answer = []

    for string in s:
        stack = []
        count_110 = 0
        for str in string:
            # 110이 나온 경우
            if(len(stack) >= 2 and stack[-1] == '1' and stack[-2] == '1' and str == '0'):
                count_110 += 1
                stack.pop()
                stack.pop()
            else:
                stack.append(str)

        # 110을 모두 제거했으므로 남은 문자열에서 연속된 1이 존재하는 곳은 한 곳밖에 없다.
        count_1 = 0
        for s in stack[::-1]:
            if s == '0':
                break
            else:
                count_1 += 1
        answer.append(''.join(stack[:len(stack) - count_1]) + '110' * count_110 + '1' * count_1)
    return answer