문제 개요
1부터 N까지의 숫자가 원형으로 배치된 링(ring)이 있다고 가정해 봅시다. 여기에 두 개의 숫자 A와 B가 주어집니다. 우리는 링 위의 임의의 위치(예: x)에 서서, x에서 A까지의 거리와 x에서 B까지의 거리의 합(Z = x→A 거리 + x→B 거리)을 계산합니다. 목표는 이 합 Z를 최소로 만드는 지점 x를 찾고, 그 최솟값을 반환하는 것입니다. 단, x는 A 또는 B와 같은 위치일 수 없다는 조건이 있습니다.
예를 들어 입력이 N = 30, A = 10, B = 20이라면 출력은 10입니다. x = 15를 선택하면 x에서 A까지의 거리는 5, x에서 B까지의 거리도 5이므로 총 거리는 5 + 5 = 10이 되기 때문입니다.
접근 방법
링은 양방향으로 이동할 수 있는 원형 구조이므로, A와 B 사이에는 두 가지 경로가 존재합니다. 즉, 시계 방향 거리와 반시계 방향 거리 중 더 짧은 쪽이 곧 최소 거리 합이 됩니다. 단, A와 B가 링에서 바로 인접해 있어 최단 거리가 1인 경우에는 그 사이에 x가 들어갈 자리가 없으므로 별도 처리가 필요합니다.
해결 절차는 다음과 같습니다.
- a > b이면 a와 b의 값을 서로 교환(swap)합니다.
- 시계 방향 거리(clock_wise_dist) := b − a
- 반시계 방향 거리(counter_clock_wise_dist) := (a − 1) + (n − b + 1)
- 최소 거리(minimum_dist) := 두 거리 중 더 작은 값
- 만약 minimum_dist가 1이라면(A와 B가 인접한 경우), x는 A나 B가 될 수 없으므로 3을 반환합니다. A 반대편 바로 옆에 서면 거리가 각각 1과 2가 되어 합이 3이 되기 때문입니다.
- 그 외의 경우에는 minimum_dist를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 동작을 더 잘 이해할 수 있습니다.
def get_min_z(n, a, b):
if (a > b):
a, b = b, a
clock_wise_dist = b - a
counter_clock_wise_dist = (a - 1) + (n - b + 1)
minimum_dist = min(clock_wise_dist, counter_clock_wise_dist)
if (minimum_dist == 1):
return 3
return minimum_dist
n = 30
a = 10
b = 20
print(get_min_z(n, a, b))입력
30, 10, 20
출력
10
동작 원리 살펴보기
N = 30, A = 10, B = 20인 경우를 따라가 보면 다음과 같습니다.
- 먼저 a < b이므로 교환 없이 진행합니다.
- 시계 방향 거리: 20 − 10 = 10
- 반시계 방향 거리: (10 − 1) + (30 − 20 + 1) = 9 + 11 = 20
- 최소 거리: min(10, 20) = 10
- 최소 거리가 1이 아니므로 최종 결과는 10
복잡도 분석
이 알고리즘은 단순한 산술 연산 몇 번만 수행하므로 시간 복잡도는 O(1), 추가 메모리 사용량 역시 O(1)입니다. 링의 크기 N이 아무리 커져도 실행 시간은 일정하게 유지되므로 매우 효율적인 해법입니다.