Python으로 주어진 초를 더하고 빼서 다시 12시로 돌아올 수 있는지 확인하는 방법

서로 다른 n개의 초(second) 값이 배열로 주어져 있다고 가정해 봅시다. 이 문제의 목표는 12시에서 출발하여 주어진 초들을 각각 정확히 한 번씩 사용해 더하거나 빼는 연산만으로 다시 12시로 돌아올 수 있는지 확인하는 것입니다.

예를 들어 입력이 seconds = [40, 90, 50]이라면 출력은 True가 됩니다. 40을 더한 후 90을 빼고, 다시 50을 더하면 원래 시점인 12시로 돌아올 수 있기 때문입니다.

문제 해결 접근 방법

이 문제는 비트마스크(bitmask) 기법을 활용한 완전 탐색으로 해결할 수 있습니다. 각 초 값에 대해 더하는 경우와 빼는 경우, 두 가지 선택지가 존재하므로 가능한 모든 조합은 2^n개입니다. 이를 비트 연산으로 효율적으로 순회할 수 있습니다.

• size := 2^(초 배열의 길이)로 설정합니다.
• c를 0부터 size-1까지 반복합니다.
  • add := 0으로 초기화합니다.
  • j를 0부터 초 배열 크기-1까지 반복합니다.
    • c AND (2^j) 결과가 0이 아니라면 add에 seconds[j]를 더합니다.
  • 그렇지 않다면 add에서 seconds[j]를 뺍니다.
• add가 (24 × 60)으로 나누어떨어진다면 True를 반환합니다.

구현 예제

다음 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(seconds):
    size = 2**len(seconds)
    for c in range(size):
        add = 0
        for j in range(len(seconds)):
            if c & (1 << j):
                add += seconds[j]
            else:
                add -= seconds[j]
        if add % (24 * 60) == 0:
            return True
    return False

seconds = [40, 90, 50]
print(solve(seconds))

입력

[40, 90, 50]

출력

True

코드 설명

위 코드에서 외부 루프 변수 c는 각 초 값을 더할지 뺄지를 결정하는 비트마스크 역할을 합니다. c의 j번째 비트가 1이면 해당 초를 더하고, 0이면 뺍니다. 하루는 24시간 × 60분 = 1440초이므로, 누적된 값이 1440으로 나누어떨어지면 시계가 정확히 한 바퀴 돌아 다시 12시에 도달했다는 의미입니다.

이 알고리즘의 시간 복잡도는 O(2^n × n)입니다. 따라서 입력 배열의 길이가 작을 때(대략 n ≤ 20 정도) 실용적으로 동작하며, 배열이 커질수록 계산량이 지수적으로 증가한다는 점을 유의해야 합니다.