Level 3 110 옮기기 Python 3

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

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

 

최종 코드

• https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_110옮기기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def move_110(s):
    stack = []
    cnt = 0
    for c in s:
        stack.append(c)
        if c == '0' and stack[-3:] == ['1', '1', '0']:
            del stack[-3:]
            cnt += 1
    idx = -1
    for i in range(len(stack)):
        if stack[i] == '0':
            idx = i
    return "".join(stack[:idx+1]) + "110"*cnt + "".join(stack[idx+1:])
    
def solution(s):
    answer = []
    for ss in s:
        answer.append(move_110(ss))
        
    return answer

---

풀이 과정

def move_110(s):
    stack = []
    
    #110 개수
    cnt = 0
    
    #문자열 s를 한 글자씩 stack에 담는다
    for c in s:
        stack.append(c)
        
        #stack의 마지막 3글자가 110인 경우,
        if c == '0' and stack[-3:] == ['1', '1', '0']:
        	#110을 삭제해주고 cnt를 카운팅 한다
            del stack[-3:]
            cnt += 1
    
    #cnt개의 110을 끼워 넣을 자리 구하기
    idx = -1
    for i in range(len(stack)):
    	#마지막 0이 있는 자리를 구한다
        if stack[i] == '0':
            idx = i
    
    #stack의 마지막 0이 있는 자리까지 문자열로 바꾸고 cnt개의 110을 깨워넣고 나머지 stack에 담긴 글자를 문자열로 바꿔서 이어붙인다
    return "".join(stack[:idx+1]) + "110"*cnt + "".join(stack[idx+1:])
    
def solution(s):
    answer = []
    for ss in s:
        answer.append(move_110(ss))
        
    return answer

#시간복잡도 = O(n^2), 공간복잡도 = O(n)