너트와 볼트 문제

다양한 너트 목록과 볼트 목록이 제공됩니다. 우리의 임무는 주어진 목록에서 너트와 볼트의 올바른 일치를 찾고 일치할 때 해당 너트를 볼트와 함께 할당하는 것입니다.

이 문제는 빠른 정렬 기술로 해결됩니다. 볼트의 마지막 요소를 피벗으로 사용하여 너트 목록을 재정렬하고 볼트가 피벗 요소인 너트의 최종 위치를 가져옵니다. 너트 목록을 분할한 후 선택한 너트를 사용하여 볼트 목록을 분할할 수 있습니다. 모든 일치 항목을 얻기 위해 왼쪽 및 오른쪽 하위 목록에 대해 동일한 작업이 수행됩니다.

입력 및 출력

Input:
The lists of locks and keys.
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Output:
After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

알고리즘

파티션(배열, 낮음, 높음, 피벗)

입력: 하나의 배열, 낮은 인덱스와 높은 인덱스, 피벗 요소.

출력: 피벗 요소의 최종 위치입니다.

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

nutAndBoltMatch(너트, 볼트, 낮음, 높음)

입력: 너트 목록, 볼트 목록, 배열의 하위 및 상위 인덱스입니다.

출력: 어떤 너트가 어떤 볼트에 해당하는지 표시합니다.

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

예

#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) {    //find location of pivot for quick sort
   int i = low;
   for(int j = low; j<high; j++) {
      if(array[j] <pivot) {    //when jth element less than pivot, swap ith and jth element
         swap(array[i], array[j]);
         i++;
      }else if(array[j] == pivot) {    //when jth element is same as pivot, swap jth and last element
         swap(array[j], array[high]);
         j--;
      }
   }
   swap(array[i], array[high]);
   return i;    //the location of pivot element
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
   if(low < high) {
      int pivotLoc = partition(nuts, low, high, bolts[high]);   //choose item from bolt to nut partitioning
      partition(bolts, low, high, nuts[pivotLoc]);    //place previous pivot location in bolt also
      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 << "After matching nuts and bolts:"<< endl;
   cout << "Nuts:  "; show(nuts, n); cout << endl;
   cout << "Bolts: "; show(bolts, n); cout << endl;
}

출력

After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^