[프로그래머스] 110 옮기기

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

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

 

시간초과 또는 예외사항으로 시간이 조금 걸렸다. 

아이디어는 '110' 을 한 번에 다 뽑은 후, 재배열하는 것이다.

 

우선 먼저 뽑은 '110' 은 사전 순이므로 '11' 앞으로 위치하거나, '0' 뒤로 위치하기 때문에 다음에 만들어지는 '110' 에 영향을 주지 않는다. 그렇기 때문에 이 방법이 가능하다.

 

'110' 을 다 뽑은 배열을 array 라고 하자. array 는 '110' 을 다 뽑았기 때문에 '1' 이 연속으로 두 개 이상 오는 경우는 '1' 이 연속적으로 오면서 '1' 로 배열이 끝나야 한다. 즉, '110' 은 array의 마지막 원소부터 역으로 '0'이 나타날 때 그 위치에 '110' 을 뽑은 개수만큼 나열해주면 사전 순으로 배열이 만들어진다. array 의 길이가 0 이거나, '0' 이 나타나지 않으면 가장 처음에 '110' 을 뽑은 개수만큼 나열하면 된다.

 

def solution(s):
    answer = []
    
    for i in s:
        array = []
        cnt = 0
        
        for j in i:
            if j == '0':
                if array[-2:] == ['1', '1']:
                    cnt = cnt + 1
                    array.pop()
                    array.pop()
                else:
                    array.append(j)
            else:
                array.append(j)
        
        if len(array) == 0:
            answer.append('110' * cnt)
        else:
            for j in range(len(array)-1, -1, -1):
                if array[j] == '0':
                    array[j] = '0' + ('110' * cnt)
                    break
                if j == 0:
                    array[j] = ('110' * cnt) + '1'
            answer.append(''.join(array))
        
    return answer
    
    print(solution(['1110','100111100','0111111010'])) # ['1101','100110110','0110110111']