프로그래머스_110 옮기기

문제

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

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

풀이

1. 문자열의 110을 모두 삭제한다.

1-1. stack에 문자열을 하나씩 넣는다.

1-2. stack의 뒤에서부터 3자리와 110을 비교한다.

 

1-2-1. 같으면 3자리를 stack에서 꺼낸다. 

 

count는 110의 개수를 저장하는 변수로,

초기 문자열 s의 길이에서 110을 제거한 stack의 길이를 이용한다. 

 

2. 문자열을 붙일 자리를 찾는다.

2-1. 문자열을 3자리씩 잘라서(temp) 110과 비교한다.

for i in range(size_stack+1) : 
    temp1 = stack[i:i+3]
    temp2 = stack[i:i+3]*3
    temp3 = (stack[i:i+3]*3)[:3]

stack이 ['1', '0', '1']이라고 하면

temp1는 ['1', '0', '1'], ['0', '1'], ['1']의 원소를 가지므로, ['1', '1', '0']과 비교하기 어렵다.

모든 경우 세 원소를 가지게 하기 위해서 각 배열을 세배로 늘려주고

앞의 세자리를 사용하도록 코드를 작성하였다.

temp1	temp2	temp3
[ '1', '0', '1' ]	[ '1', '0', '1', '1', '0', '1', '1', '0', '1' ]	[ '1', '0', '1' ]
[ '0', '1' ]	[ '0', '1', '0', '1', '0', '1' ]	[ '0', '1', '0' ]
[ '1' ]	[ '1' , '1', '1' ]	[ '1', '1', '1' ]

i = size_stack인 경우 temp1은 [] 빈 리스트를 가진다. 이를 이용하여

i = size_stack-1일 때 110보다 큰 temp를 찾은 경우와

문자열 전체에서 110보다 큰 temp를 찾지 못한 경우를 분리할 수 있다.

 

2-2. 잘린 문자열 temp가 110보다 크면

해당 위치에 1에서 제거한 110을 끼워 붙인다. 

 

코드

def f(s) : 
    p = list('110')
    size_s = len(s)

    # 110 제거하기
    count = 0
    stack = list()
    for i in range(size_s) : 
        stack.append(s[i])
        if stack[-3:] == p : 
            stack.pop()
            stack.pop()
            stack.pop()

    size_stack = len(stack)
    count = int((size_s-size_stack)/3)

    # 110 붙이기
    for i in range(size_stack+1) : 
        temp = (stack[i:i+3]*3)[:3]
        if temp>p : break

    new_s = stack[:i] + p*count + stack[i:]    
    return ''.join(new_s)
    
def solution(arr):
    answer = [f(s) for s in arr]        
    return answer