프로그래머스 [Lv. 3] 110 옮기기 {언어 : Python} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

from collections import deque
def solution(s):
    answer = []
    lenS = len(s)
    for i in range(lenS):
        q = deque(s[i])
        stack = []
        ooz = 0
        ooo = 0
        
        # 110 찾기
        while q:
            tmp = q.popleft()
            stack.append(tmp)
            if len(stack) >= 3:
                if stack[-3] == "1" and stack[-2] == "1" and stack[-1] == "0":
                    for _ in range(3):
                        stack.pop()
                    ooz += 1
        
        # 110 빼고 나머지에서 111 찾기
        q = deque(stack)
        stack = []
        while q:
            tmp = q.popleft()
            stack.append(tmp)
            if len(stack) >= 3:
                if stack[-3] == "1" and stack[-2] == "1" and stack[-1] == "1":
                    for _ in range(3):
                        stack.pop()
                    ooo += 1
    
        # 오른쪽부터 탐색하면서 0을 찾음
        # 찾고 나서 합치기
        stringBuilder = []
        lenS = len(stack)
        rIdx = 0
        if lenS:
            for j in range(len(stack)-1, -1, -1):
                if stack[j] == "0":
                    rIdx = j + 1
                    break
            stringBuilder += stack[:rIdx]
            
        for _ in range(ooz):
            stringBuilder.append("110")
        for _ in range(ooo):
            stringBuilder.append("111")
            
        if lenS:
            stringBuilder += stack[rIdx:]
        
        newString = "".join(stringBuilder)
        answer.append(newString)
            
    return answer

풀이 방법

1. 110이 안나올 때까지 찾아서 뺀다.
   1. 빼면서 개수를 측정한다. ooz (one-one-zero)
2. 111이 안 나올 때까지 찾아서 뺀다.
   1. 빼면서 개수를 측정한다. ooo (one-one-one)
3. 남은 stack에 0의 위치를 찾는다.
   1. 110도 결국엔 0 보다 사전순으로 봤을 때 뒤이기 때문이다.
4. 0 뒤에 110을 ooz만큼 곱해서 넣고 111도 넣어준다.
5. join 함수를 이용해서 문자열을 만들고 answer에 넣어주면 끝!

느낀점

• find 함수 사용하면 시간을 단축 시킬 수 있다.
• 메모리는 덜 쓴 것 같다.