[프로그래머스] 110 옮기기

문제

• 0과 1로 이루어진 문자열 x에서 "110"을 뽑아 임의 위치에 다시 삽입함으로써 최대한 사전 순으로 앞에 오도록 만들고자 한다.
• 예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 된다.
  뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 된다.
• 변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어질 때 각 문자열에 대해 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 리턴하기
  • 1 <= s의 길이 <= 1,000,000
  • 1 <= x의 길이 <= 1,000,000

 

풀이

• 시간 복잡도
  • 원소 개수가 최대 100만개 이므로, 각 원소에 대해 최소 40번 연산 안에 수행해야 한다.
  • 40번 연산 안에 최대 길이 100만의 문자열 x에 대해 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열 찾아야한다.
• "110" 의 위치를 모두 찾고, 적절한 위치에 삽입하기
  
  • 110 보다 사전 순으로 뒤에 있는 문자열은 111 밖에 없다.
  • 즉, 모든 110을 111 앞에 삽입하거나 111이 없다면 0 뒤에 반복해 붙이면 된다.

 

def solution(s):
    answer = []
    for string in s:
        count, idx, stack, n = 0, 0, "", len(string)

        # 110 찾기
        for idx in range(n):          
            if string[idx] == "0" and stack[-2:] == "11":
                stack = stack[:-2]
                count += 1
            else:
                stack += string[idx]

        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

 

 

예시

"1100111011101001" => "0101101101101101"

 

 

References

• 프로그래머스 Lv3 110 옮기기
• TikTaek/ 110 옮기기