문제

킥다운은 자동차의 기어를 손으로 조작하지 않고 페달을 밟음으로써 기어를 변속하는 장치이다. 두 기어가 맞물리기 위해서는 두 기어의 이가 서로 맞물려야 한다.

두 기어의 이 배열이 주어질 때, 최소 길이로 맞물릴 수 있도록 하는 길이를 구하는 프로그램을 작성하시오.

풀이

브루트포스로 모든 위치를 시도하여 최소 길이를 구하는 문제이다.

코드

gear1 = list(map(int, list(input().strip())))
gear2 = list(map(int, list(input().strip())))

len1 = len(gear1)
len2 = len(gear2)

if len1 > len2:
    gear1, gear2 = gear2, gear1
    len1, len2 = len2, len1

min_total_length = len1 + len2

for start in range(-len1 + 1, len2):
    
    for i in range(len1):
        gear2_idx = start + i
        if 0 <= gear2_idx < len2:
            # 두 개의 이가 맞물리면 안됨
            if gear1[i] == 2 and gear2[gear2_idx] == 2:
                break

    else:
        current_length = max(len2, start + len1) - min(0, start)
        min_total_length = min(min_total_length, current_length)

print(min_total_length)

시간 복잡도

O(N^2)