[programmers] 110 옮기기

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

x에 있는 “110”을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 들어, x = “11100” 일 때, 여기서 중앙에 있는 “110”을 뽑으면 x = “10” 이 됩니다. 뽑았던 “110”을 x의 맨 앞에 다시 삽입하면 x = “11010” 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ s의길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

입출력 예

s	results
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

입출력 예 설명

• 생략

Idea

이해하는데 어려웠고, 문제 해결방법을 찾는데도 어려웠다. 구현은 뭐 말할것도 없다.
일단 어떻게 접근했는지 부터 설명을 해보면,

1. 110이라는 패턴을 주어지 문자열에서 모두 찾는것
2. 남은 문자열에서 ‘0’뒤에 110을 넣어준다. 갯수만큼
3. 남은 문자열에서 ‘0’이 없다면 가장 앞에 넣어준다.갯수만큼

Code

from collections import deque
def solution(s):
    answer = list()
    for string in s:
        temp = list()
        count = 0
        for char in string:
            if char == '0':
                if temp[-2:] == ['1', '1']:
                    count += 1
                    temp.pop()
                    temp.pop()
                else:
                    temp.append(char)
            else:
                temp.append(char)
                
        # print(temp)
        if count == 0:
            answer.append(string)
        else:
            final = deque()
            while temp:
                if temp[-1] == '1':
                    final.append(temp.pop())
                elif temp[-1] == '0':
                    break

            while count > 0:
                final.appendleft('0')
                final.appendleft('1')
                final.appendleft('1')
                count -= 1

            while temp:
                final.appendleft(temp.pop())
            answer.append(''.join(final))
        
    return answer

Explain

아이디어 부분은 제일 좋은데, 코드가 너무 길다. 다음에 다시 풀어 봐야 겠다.

References

• https://yabmoons.tistory.com/668