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

문제 요약

0과 1로 이루어진 문자열에서 다음 동작을 원하는 만큼 수행할 수 있다.

문자열에 있는 "110"을 제거한다.
제거한 "110"을 문자열의 원하는 위치에 다시 삽입한다.

각 문자열을 만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열로 변환해야 한다.

문자열 배열 s의 각 원소에 대해 변환 결과를 배열에 담아 반환한다.

핵심 아이디어

문제를 다음 두 단계로 나누어 생각할 수 있다.

1. 문자열에서 만들 수 있는 모든 "110"을 제거한다.
2. 제거한 "110"들을 사전순으로 가장 유리한 위치에 다시 삽입한다.

문자열에서 모든 "110"을 제거할 때는 스택을 사용한다.

문자를 하나씩 스택에 넣고, 스택의 마지막 세 문자가 "110"이 되면 즉시 제거한다.

제거 과정이 끝난 문자열에는 더 이상 "110"이 존재하지 않는다.

제거한 "110"들은 남은 문자열의 마지막 0 바로 뒤에 모두 삽입해야 사전순으로 가장 앞선 문자열이 된다.

남은 문자열에 0이 없다면 모든 "110"을 문자열 맨 앞에 삽입한다.

사전순 비교

이진 문자열에서는 같은 위치의 문자를 비교할 때 0이 1보다 앞선다.

0 < 1

따라서 가능한 한 앞쪽에 0이 등장하는 문자열이 사전순으로 더 작다.

"110"은 1로 시작하기 때문에 남아 있는 0보다 앞에 삽입하면 그 0의 위치를 뒤로 밀게 된다.

예를 들어 다음 두 문자열을 비교해보자.

1100
0110

첫 번째 문자에서 0이 등장하는 0110이 더 앞선다.

따라서 제거한 "110"을 남아 있는 0들보다 앞에 배치하면 손해다.

반대로 마지막 0보다 뒤에는 1들만 남는다.

이 1들보다 "110"을 앞에 놓으면 "110" 안의 0이 더 일찍 등장한다.

예를 들어 다음 두 문자열을 비교해보자.

1101
1110

세 번째 문자에서 0이 등장하는 1101이 더 앞선다.

따라서 최적의 삽입 위치는 다음과 같다.

남은 문자열의 모든 0 뒤
남은 문자열 끝의 연속된 1 앞

즉, 마지막 0 바로 뒤다.

모든 110 제거하기

단순히 문자열에서 find와 슬라이싱을 반복하면 제거할 때마다 새로운 문자열이 만들어질 수 있다.

문자열 길이가 크면 비효율적이므로 스택을 사용한다.

문자를 하나씩 스택에 추가한다.

stack.append(character)

스택의 마지막 세 문자가 1, 1, 0이면 "110"이 완성된 것이다.

if (
    len(stack) >= 3
    and stack[-3] == "1"
    and stack[-2] == "1"
    and stack[-1] == "0"
):

마지막 세 문자를 제거하고 개수를 증가시킨다.

del stack[-3:]
count_110 += 1

문자를 순서대로 넣으면서 바로 검사하기 때문에, "110"을 제거한 결과 새롭게 만들어지는 "110"도 놓치지 않는다.

110을 다시 삽입하기

스택에 남은 문자들을 하나의 문자열로 만든다.

remaining = "".join(stack)

마지막 0의 위치를 찾는다.

insert_position = remaining.rfind("0") + 1

rfind("0")은 마지막 0의 인덱스를 반환한다.

여기에 1을 더하면 마지막 0 바로 뒤의 위치가 된다.

남은 문자열에 0이 없다면 rfind는 -1을 반환한다.

-1 + 1 = 0

따라서 별도의 조건문 없이 문자열 맨 앞인 0번 위치에 삽입할 수 있다.

제거한 개수만큼 "110"을 이어 붙인다.

moved = "110" * count_110

마지막으로 세 부분을 합친다.

result = (
    remaining[:insert_position]
    + moved
    + remaining[insert_position:]
)

풀이 과정

1. 각 문자열을 순회

for string in s:

문자열마다 독립적으로 최솟값을 구한다.

2. 스택과 제거 개수 초기화

stack = []
count_110 = 0

3. 문자를 스택에 추가

for character in string:
    stack.append(character)

4. 스택 끝의 110 제거

if (
    len(stack) >= 3
    and stack[-3] == "1"
    and stack[-2] == "1"
    and stack[-1] == "0"
):
    del stack[-3:]
    count_110 += 1

5. 마지막 0 뒤에 삽입

remaining = "".join(stack)
insert_position = remaining.rfind("0") + 1

converted = (
    remaining[:insert_position]
    + "110" * count_110
    + remaining[insert_position:]
)

6. 결과 배열에 추가

answer.append(converted)

Python 코드

def solution(s):
    answer = []

    for string in s:
        stack = []
        count_110 = 0

        # 문자열에서 만들 수 있는 모든 "110"을 제거한다.
        for character in string:
            stack.append(character)

            if (
                len(stack) >= 3
                and stack[-3] == "1"
                and stack[-2] == "1"
                and stack[-1] == "0"
            ):
                del stack[-3:]
                count_110 += 1

        remaining = "".join(stack)

        # 마지막 0 바로 뒤에 제거한 "110"들을 삽입한다.
        # 0이 없으면 rfind가 -1을 반환하므로 삽입 위치는 0이 된다.
        insert_position = remaining.rfind("0") + 1

        converted = (
            remaining[:insert_position]
            + "110" * count_110
            + remaining[insert_position:]
        )

        answer.append(converted)

    return answer

코드 설명

스택 사용

stack = []

현재까지 확인한 문자 중 아직 제거되지 않은 문자들을 저장한다.

리스트의 마지막 부분만 확인하고 제거하므로 문자열을 계속 새로 만드는 방식보다 효율적이다.

마지막 세 문자 확인

stack[-3] == "1"
stack[-2] == "1"
stack[-1] == "0"

스택에 새 문자가 추가될 때 새롭게 생길 수 있는 "110"은 반드시 스택의 끝에 있다.

따라서 전체 스택을 다시 탐색하지 않고 마지막 세 문자만 확인하면 된다.

슬라이스 삭제

del stack[-3:]

스택의 마지막 세 문자를 한 번에 제거한다.

다음과 같이 세 번 pop을 호출해도 같은 결과를 얻을 수 있다.

stack.pop()
stack.pop()
stack.pop()

마지막 0 탐색

insert_position = remaining.rfind("0") + 1

마지막 0보다 앞에는 제거한 "110"을 넣지 않는다.

마지막 0 뒤에 있는 연속된 1들보다는 "110"을 앞에 배치한다.

이 위치가 사전순으로 가장 작은 결과를 만든다.

110이 없는 경우

"110" * count_110

count_110이 0이라면 빈 문자열이 만들어진다.

따라서 별도의 예외 처리 없이 원래 문자열이 그대로 결과에 들어간다.

예시

다음 입력을 살펴보자.

s = [
    "1110",
    "100111100",
    "0111111010"
]

1110

"110"을 하나 제거하면 "1"이 남는다.

남은 문자열에는 0이 없으므로 "110"을 맨 앞에 삽입한다.

110 + 1 = 1101

100111100

모든 "110"을 제거하면 "100"이 남고, "110"은 두 개 제거된다.

마지막 0 뒤에 두 개를 삽입한다.

100 + 110 + 110
= 100110110

0111111010

모든 "110"을 제거하면 "0111"이 남고, "110"은 두 개 제거된다.

마지막 0 바로 뒤에 삽입한다.

0 + 110 + 110 + 111
= 0110110111

따라서 결과는 다음과 같다.

[
    "1101",
    "100110110",
    "0110110111"
]

시간 복잡도

문자열들의 전체 길이 합을 L이라고 하자.

각 문자는 스택에 한 번 들어가고, "110"에 포함된 문자는 한 번 제거된다.

남은 문자열 생성과 마지막 0 탐색도 각 문자열 길이에 비례한다.

O(L)

문자열에서 "110"을 찾고 제거하는 작업을 반복하지 않으므로 큰 입력도 효율적으로 처리할 수 있다.

공간 복잡도

각 문자열의 제거되지 않은 문자들을 스택에 저장한다.

가장 긴 문자열의 길이를 M이라고 하면 다음과 같다.

O(M)

반환할 결과 문자열 배열에 필요한 공간은 별도다.

정리

이 문제는 스택으로 특정 문자열을 모두 제거한 뒤 사전순으로 가장 유리한 위치에 다시 삽입하는 그리디 문제다.

풀이 흐름은 다음과 같다.

문자를 하나씩 스택에 추가
스택 끝이 "110"이면 즉시 제거하고 개수 기록
제거가 끝난 문자열에서 마지막 0의 위치 탐색
마지막 0 바로 뒤에 모든 "110" 삽입
0이 없다면 문자열 맨 앞에 삽입

새로운 "110"이 만들어지는 상황까지 스택으로 빠짐없이 제거하는 것과, 남은 0들의 뒤이면서 끝의 연속된 1들 앞에 "110"을 배치하는 것이 핵심이다.