[프로그래머스] 코딩테스트 연습 - 110 옮기기 (Python)

코딩 테스트 연습 - 110 옮기기 [월간 코드 챌린지 시즌2]

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

문제를 이해하는 것부터 쉽지 않았는데 시간 초과를 해결하는 것도 쉽지만은 않았네요ㅎㅎ..

 

풀이

문제를 해결한 방법을 간단하게 말하면 아래와 같습니다.

1. 110을 모두 찾아서 가장 왼쪽에 있는 111 앞에 넣습니다.

 

문제의 목표는 110을 뽑고 임의의 위치에 삽입해서 사전 순으로 가장 앞에 오도록 하는 것입니다.

사전 순으로는 0이 1보다 먼저 검색되므로 110보다 사전 순으로 늦게 검색되는 문자열은 111밖에 없겠죠.

\( \Rightarrow \) 111보다 110이 먼저 검색된다.

그러므로 110을 모두 찾아서 111 앞에 삽입한다면 111을 110으로 대체한 것과 같은 효과가 생기는 것이죠.

 

110을 모두 추출하고 남은 문자열을 string이라고 하고 string에서 111이 없다면 가능하면 string의 뒤쪽에 111이 생기지 않도록 110을 삽입해야 합니다.

예를 들어보면 string이 101이고 string의 가장 뒤에 110을 붙이면 101110이 됩니다. 110을 삽입한 위치의 바로 앞 문자가 1이기 때문에 새로운 111이 발생하게 되는 것이죠. 111이 발생하지 않기 위해서는 10 + 110 + 1 = 101101으로 삽입하면 됩니다.

\( \Rightarrow \) 110을 삽입한 후에 새로운 111이 발생하지 않도록 string에서 가장 뒤쪽에 있는 0 뒤에 110을 삽입한다.

 

 

Code

def solution(s):
    answer = []
    for string in s:
        count, idx, stack = 0, 0, ""
        while idx < len(string):            # 110 찾기
            if string[idx] == "0" and stack[-2:] == "11":
                stack = stack[:-2]
                count += 1
            else:
                stack += string[idx]
            idx += 1

        idx = stack.find("111")             # 110이 빠진 string에서 111 찾기
        if idx == -1:                       # 0뒤에 110 반복해 붙이기
            idx = stack.rfind('0')
            stack = stack[:idx+1]+"110"*count+stack[idx+1:]
        else:                               # 111앞에 110 반복해 붙이기
            stack = stack[:idx]+"110"*count+stack[idx:]
        answer.append(stack)
    return answer

 

 

문제 설명

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	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

 

입출력 예 #1

• 다음 그림은 "1110"을 "1101"로 만드는 과정을 나타낸 것입니다.

• "1101"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "1101"을 담아야 합니다.
• 다음 그림은 "100111100"을 "100110110"으로 만드는 과정을 나타낸 것입니다.

• "100110110"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "100110110"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "100110110"을 만들 수 있습니다.
• 다음 그림은 "0111111010"을 "0110110111"로 만드는 과정을 나타낸 것입니다.

• "0110110111"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "0110110111"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다.