title: "[프로그래머스] 110 옮기기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/77886"
description: "프로그래머스 Level 3 문제 [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

아이디어 및 해결 방법

문제를 해결하기 위해서 중요한 관찰은, 110을 문자열에 삽입해서 새로 110이 나타나는 경우가 없다는 것입니다.

맨 앞이나 맨 뒤에 들어갔을 때는 자명하게 110이 새로 나타날 수가 없고, 아래와 같이 임의의 두 숫자 사이에 들어가는 경우의 수 4가지를 모두 고려해보아도 그렇습니다.

0 110 0 # 0과 0 사이에 들어가는 경우
0 110 1 # 0과 1 사이에 들어가는 경우
1 110 0 # 1과 0 사이에 들어가는 경우
1 110 1 # 1과 1 사이에 들어가는 경우

즉, 이 관찰에 의해서 문자열에서 나타나는 110들을 모두 제거한 다음, 110을 채워넣는 식으로 진행해도 제거-삽입을 섞어서 진행하는 방식과 동일한 결과를 반드시 얻을 수 있다는 것을 알 수 있습니다.

이제 (1) 110을 모두 제거하고, (2) 최적의 배치로 110을 채워넣는 순서로 문제를 단순화해서 풀 수 있겠네요!

110을 모두 제거하는 방법

스택 하나를 관리합니다. 문자열을 앞에서부터 읽어가면서 숫자를 하나하나 스택에 push합니다.