Python으로 전구 스위치 문제 해결하기: 바이너리 문자열 기반 최소 플립 횟수 구하기

방에 n개의 전구가 있다고 가정해 보겠습니다. 전구들은 0부터 n-1까지 번호가 매겨져 있으며, 왼쪽에서 오른쪽으로 한 줄로 배치되어 있습니다. 처음에는 모든 전구가 꺼져 있는 상태(0)입니다. 우리의 목표는 주어진 목표 배열 t로 표현되는 구성을 만드는 것입니다. 여기서 t[i]는 i번째 전구가 켜져 있으면 '1', 꺼져 있으면 '0'을 의미합니다.

또한 전구의 상태를 반전시키는 스위치가 하나 있으며, 플립(flip) 연산은 다음과 같이 정의됩니다.

임의의 전구 인덱스 i를 선택합니다.
인덱스 i부터 n-1까지의 모든 전구 상태를 반전시킵니다.

목표 상태를 만들기 위해 필요한 최소 플립 횟수를 구해야 합니다.

예를 들어 입력이 t = "0101"이라면 출력은 3이 됩니다. 두 번째 전구부터 플립하면 "0111"이 되고, 이어서 세 번째부터 플립하면 "0100"이 되며, 마지막으로 마지막 전구를 플립하면 "0101"이 되기 때문입니다.

해결 접근 방법

이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 플립 연산이 항상 선택한 위치부터 끝까지 모든 전구를 반전시키기 때문에, 왼쪽에서 오른쪽으로 전구를 살펴볼 때 인접한 비트의 상태가 바뀌는 지점(경계)마다 플립이 한 번씩 필요합니다. 따라서 상태 변화가 일어나는 지점의 개수만 세면 곧 최소 플립 횟수가 됩니다.

구체적인 알고리즘은 다음과 같습니다.

count = 0, x = '0'으로 초기화합니다. (초기 상태는 모두 꺼짐이므로 x는 '0'에서 시작)
t의 각 문자 i에 대해 다음을 수행합니다.
- i가 x와 다르다면 count를 1 증가시키고, x = i로 갱신합니다.
모든 순회가 끝나면 count를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

def solve(t):
    count = 0
    x = '0'
    for i in t:
        if i != x:
            count += 1
            x = i
    return count

t = "0101"
print(solve(t))

입력

"0101"