0과 1로 이루어진 이진 문자열 input_str이 주어졌다고 가정해 보겠습니다. 우리가 해야 할 작업은 문자열 안의 1들을 서로 교환(swap)하여 0과 1을 각각 그룹으로 모으는 것이며, 이때 필요한 스왑 연산 횟수를 최소화하고 그 최솟값을 반환하는 것입니다.
여기서 중요한 제약 조건은 하나 있습니다. 바로 인접한 값끼리만 스왑할 수 있다는 점입니다.
예를 들어 입력이 input_str = '10110101'이라면 출력은 4가 됩니다. 실제 스왑 과정은 다음과 같습니다.
10110101 → 01110101 → 01111001 → 01111010 → 01111100
총 스왑 횟수는 4회입니다.
문제 해결 접근 방식
이 문제의 핵심 아이디어는 중앙값(median)에 기반한 접근입니다. 직선 위의 여러 지점을 한곳으로 모을 때 총 이동 거리를 최소화하려면 중앙값 위치를 목표로 삼아야 하듯이, 모든 1을 연속된 구간으로 모을 때도 마찬가지 원리가 적용됩니다.
구체적인 단계는 다음과 같습니다.
one: 문자열에서 1이 위치한 인덱스들을 순서대로 저장한 리스트를 만듭니다.mid: 리스트one길이를 2로 나눈 값의 내림(floor)을 구합니다. 즉, 중앙에 있는 1의 인덱스입니다.res: 결과값을 저장할 변수로 0으로 초기화합니다.- i를 0부터
one의 길이까지 반복하면서 다음을 누적합니다.res += abs(one[mid] - one[i]) - abs(mid - i)
- 반복이 끝난 후
res < 0이면 0을 반환하고, 그렇지 않으면res를 반환합니다.
여기서 abs(one[mid] - one[i])는 현재 1이 목표 위치까지 실제로 이동해야 하는 거리이고, abs(mid - i)는 그룹화된 상태에서 해당 1이 차지해야 할 상대적 자리를 의미합니다. 두 값의 차이를 모두 더하면 순수하게 추가로 필요한 스왑 횟수가 됩니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(input_string):
one = [i for i in range(len(input_string)) if input_string[i] == "1"]
mid = len(one) // 2
res = 0
for i in range(len(one)):
res += abs(one[mid] - one[i]) - abs(mid - i)
return 0 if res < 0 else res
print(solve('10110101'))입력
'10110101'
출력
4
복잡도 분석
이 알고리즘은 문자열을 한 번 순회하여 1의 위치를 찾고(O(n)), 다시 1의 개수만큼 반복하므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 1의 위치를 저장하는 리스트 때문에 최악의 경우 O(n)입니다. 인접 스왑만 허용되는 제약 조건 속에서도 매우 효율적으로 최솟값을 계산할 수 있는 방법입니다.