너트와 볼트 매칭 문제: 퀵 정렬로 짝 찾기

서로 다른 너트(nut) 목록과 볼트(bolt) 목록이 각각 주어졌을 때, 두 목록에서 서로 올바르게 맞는 너트와 볼트의 짝을 모두 찾아내고, 일치하는 너트를 해당 볼트에 할당하는 것이 이 문제의 목표입니다.

이 문제는 퀵 정렬(Quick Sort) 기법으로 효율적으로 해결할 수 있습니다. 먼저 볼트 목록의 마지막 요소를 피벗(pivot)으로 삼아 너트 목록을 분할(partition)하면, 그 볼트와 짝이 되는 너트의 최종 위치를 알 수 있습니다. 너트 목록의 분할이 끝나면, 이번에는 선택된 너트를 피벗으로 사용해 볼트 목록을 분할합니다. 이후 왼쪽 부분 목록과 오른쪽 부분 목록에 대해 같은 과정을 재귀적으로 반복하면 모든 너트-볼트 짝을 찾을 수 있습니다.

핵심 아이디어는 너트끼리는 서로 비교할 수 없고, 볼트끼리도 서로 비교할 수 없으며, 오직 너트와 볼트 사이의 비교만 가능하다는 제약 조건입니다. 퀵 정렬의 분할 과정을 양쪽 목록에 교차로 적용하면 이 제약 조건 안에서도 정렬과 매칭을 동시에 수행할 수 있습니다.

입력 및 출력

입력:
너트 목록과 볼트 목록
nuts = { ),@,*,^,(,%,!,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }

출력:
너트와 볼트 매칭 후:
너트:  ! # $ % & ( ) * @ ^
볼트: ! # $ % & ( ) * @ ^

알고리즘

1. partition(array, low, high, pivot)

입력: 하나의 배열, low·high 인덱스, 피벗 요소

출력: 피벗 요소의 최종 위치

Begin
    i := low
    for j in range low to high, do
        if array[j] < pivot, then
            swap array[i] and array[j]
            increase i by 1
        else if array[j] = pivot, then
            swap array[j] and array[high]
            decrease j by 1
    done

    swap array[i] and array[high]
    return i
End

2. nutAndBoltMatch(nuts, bolts, low, high)

입력: 너트 목록, 볼트 목록, 배열의 low·high 인덱스

출력: 어떤 너트가 어떤 볼트와 짝인지 출력

Begin
    pivotLoc := partition(nuts, low, high, bolts[high])
    partition(bolts, low, high, nuts[pivotLoc])
    nutAndBoltMatch(nuts, bolts, low, pivotLoc-1)
    nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high)
End

동작 순서를 정리하면 다음과 같습니다. 첫째, 볼트의 마지막 요소를 피벗으로 너트 배열을 분할하여 피벗 너트의 위치(pivotLoc)를 구합니다. 둘째, 그 위치에 있는 너트를 피벗으로 볼트 배열을 분할하면 두 배열의 같은 인덱스에 짝이 놓이게 됩니다. 셋째, pivotLoc을 기준으로 왼쪽과 오른쪽 부분 배열에 대해 재귀 호출을 수행해 전체 매칭을 완성합니다.

C++ 예제 코드

#include<iostream>
using namespace std;

void show(char array[], int n) {
    for(int i = 0; i<n; i++)
        cout << array[i] << " ";
}

int partition(char array[], int low, int high, char pivot) {   //피벗의 최종 위치를 찾음
    int i = low;
    for(int j = low; j<high; j++) {
        if(array[j] <pivot) {          //j번째 요소가 피벗보다 작으면 i번째와 교환
            swap(array[i], array[j]);
            i++;
        }else if(array[j] == pivot) {  //j번째 요소가 피벗과 같으면 마지막 요소와 교환
            swap(array[j], array[high]);
            j--;
        }
    }
    swap(array[i], array[high]);
    return i;                          //피벗 요소의 위치 반환
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
    if(low < high) {
        int pivotLoc = partition(nuts, low, high, bolts[high]); //볼트의 마지막 요소로 너트 분할
        partition(bolts, low, high, nuts[pivotLoc]);            //같은 너트로 볼트 분할
        nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1);
        nutAndBoltMatch(nuts, bolts, pivotLoc+1, high);
    }
}

int main() {
    char nuts[] = {')','@','*','^','(','%','!','$','&','#'};
    char bolts[] = {'!','(','#','%',')','^','&','*','$','@'};
    int n = 10;
    nutAndBoltMatch(nuts, bolts, 0, n-1);
    cout << "너트와 볼트 매칭 후:"<< endl;
    cout << "너트:  "; show(nuts, n); cout << endl;
    cout << "볼트: "; show(bolts, n); cout << endl;
}

실행 결과

너트와 볼트 매칭 후:
너트:  ! # $ % & ( ) * @ ^
볼트: ! # $ % & ( ) * @ ^

결과를 보면 너트와 볼트가 동일한 순서(! # $ % & ( ) * @ ^)로 정렬되어, 같은 인덱스에 있는 너트와 볼트가 서로 짝임을 한눈에 확인할 수 있습니다. 여기서 문자의 정렬 순서는 아스키(ASCII) 코드 값을 기준으로 결정됩니다.

시간 복잡도

평균적인 경우 시간 복잡도는 O(n log n)이며, 이미 정렬된 입력처럼 분할이 한쪽으로 치우치는 최악의 경우에는 O(n²)입니다. 공간 복잡도는 재귀 호출 스택에 의해 평균 O(log n), 최악의 경우 O(n)입니다.