[프로그래머스]Lv3. 110 옮기기(Python)

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

프로그래머스

 

문제 접근 

 

1. 110을 모두 찾은 후 111 앞에 넣는다. => 111보다 110이 먼저 검색된다.
2. 110을 모두 추출하고 남은 문자열에서 가능하면 111이 생기지 않도록 110을 삽입해야 한다.
   • 101에 110을 붙이면 101110 => 111 발생
   • 가장 뒤쪽에 있는 0 뒤에 110 삽입 => 101101

코드

def solution(s):
    answer = []
    
    for string in s:
        cnt, idx, stack = 0, 0, ""  # cnt: '110'의 개수, idx: 현재 인덱스, stack:문자열 임시 저장
        while idx < len(string):    # 문자열 끝까지 탐색
            if string[idx] == "0" and stack[-2:] == "11": # 현재 문자가 '0'이고 이전 문자가 '11'인 경우 => '110'
                stack = stack[:-2]   # 찾은 '110'을 stack에서 제거
                cnt += 1
            else:
                stack += string[idx]    # '110'이 생기지 않는 경우 stack에 추가
                
            idx += 1
        
        idx_111 = stack.find("111") # stack에서 '111'을 찾음
        if idx_111 == -1:   # '111'이 없으면 
            idx_111 = stack.rfind('0')  # 가장 뒤에 있는 0을 찾아서 삽입(2번)
            stack = stack[:idx_111+1] + "110"*cnt + stack[idx_111+1:]
        else:   # '111'이 있으면 그 앞에 '110'을 cnt만큼 붙임(1번)
            stack = stack[:idx_111] + "110"*cnt + stack[idx_111:]
        
        answer.append(stack)
    
    return answer