두 개의 숫자 a와 b가 주어졌을 때, [1, a] 범위의 값을 모두 포함하면서 재귀 병합 정렬 함수가 정확히 b번 호출되도록 만드는 배열을 찾는 문제입니다.
예를 들어 입력이 a = 10, b = 15라면, 가능한 출력 중 하나는 [3, 1, 4, 6, 2, 8, 5, 9, 10, 7]입니다.
핵심 아이디어
이미 정렬된 배열에 병합 정렬을 수행하면 최초 호출 단 한 번만 실행됩니다. 반면 인접한 두 원소의 순서를 뒤바꿀 때마다 분할 과정에서 추가적인 재귀 호출이 2번씩 발생합니다. 따라서 병합 정렬의 총 호출 횟수는 항상 홀수가 되며, b가 짝수라면 조건을 만족하는 배열은 존재하지 않습니다.
해결 알고리즘
다음 단계에 따라 문제를 해결할 수 있습니다.
- solve() 함수를 정의합니다. 이 함수는 left, right, array, b를 매개변수로 받습니다.
- b < 1이거나 left + 1 == right이면 함수를 종료(return)합니다.
- b를 2만큼 감소시킵니다. (b -= 2)
- mid = (left + right) // 2로 중간 지점을 계산합니다.
- array[mid - 1]과 array[mid]의 값을 서로 교환(swap)합니다.
- solve(left, mid, array, b)와 solve(mid, right, array, b)를 재귀적으로 호출합니다.
메인 메서드 처리 과정
- b % 2 == 0이라면 "None"을 출력하고 종료합니다. (호출 횟수는 항상 홀수여야 하므로)
- 크기가 n + 1인 배열을 생성하고 0으로 초기화합니다.
- array[0] = 1로 설정하고, i가 1부터 a-1까지 array[i] = i + 1을 대입합니다.
- b에서 1을 뺍니다. (최초 호출 1회 차감)
- solve(0, a, array, b)를 호출합니다.
- 최종적으로 array와 a를 반환합니다.
구현 예시
더 나은 이해를 위해 파이썬 구현 코드를 살펴보겠습니다.
def solve(left, right, array, b):
if (b < 1 or left + 1 == right):
return
b -= 2
mid = (left + right) // 2
temp = array[mid - 1]
array[mid - 1] = array[mid]
array[mid] = temp
solve(left, mid, array, b)
solve(mid, right, array, b)
def find_arr(a, b):
if (b % 2 == 0):
print("None")
return
array = [0 for i in range(a + 2)]
array[0] = 1
for i in range(1, a):
array[i] = i + 1
b -= 1
solve(0, a, array, b)
return array, a
a = 10
b = 15
array, size = find_arr(a, b)
print(array[:size])입력
10, 15출력
[3, 1, 4, 6, 2, 8, 5, 9, 10, 7]마무리
이 알고리즘은 병합 정렬의 분할 구조를 역으로 활용합니다. 정렬된 상태에서 시작해 중간 지점의 인접 원소를 교환할 때마다 재귀 호출 횟수가 2씩 증가한다는 성질을 이용하면, 원하는 호출 횟수 b에 정확히 맞는 배열을 손쉽게 구성할 수 있습니다.