C++를 사용하여 N을 25로 나눌 수 있도록 하는 데 필요한 최소 이동 횟수입니다.

문제 설명

선행 0이 없는 숫자 N이 주어집니다. 작업은 N을 25로 나누는 데 필요한 최소 이동 횟수를 찾는 것입니다. 각 이동에서 두 개의 인접한 숫자를 바꿀 수 있으며 항상 숫자에 선행 0이 포함되어서는 안 됩니다. N을 25로 나눌 수 없으면 -1을 인쇄하십시오.

N =5071이면 25로 나누어 떨어지도록 4번 이동해야 합니다.

5071 → 5701 → 7501 → 7510 → 7150

알고리즘

1. Iterate over all pairs of digits in the number. Let the first digit in the pair is at position ‘i’ and the second is at position ‘j’.
2. Place these digits to the last two positions in the number
3. If the number has a leading zero. Find the leftmost nonzero digit and move it to the first position.
4. If the current number is divisible by 25 then update the answer with the number of swaps

예시

#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;
int requiredMoves(long long n){
   string str = to_string(n);
   int ans = INT_MAX;
   int len = str.size();
   for (int i = 0; i < len; ++i) {
      for (int j = 0; j < len; ++j) {
         if (i == j)
            continue;
      string temp = str;
      int cnt = 0;
      for (int k = i; k < len - 1; ++k) {
         swap(temp[k], temp[k + 1]);
         ++cnt;
      }
      for (int k = j - (j > i); k < len - 2; ++k) {
         swap(temp[k], temp[k + 1]);
         ++cnt;
      }
      int pos = -1;
      for (int k = 0; k < len; ++k) {
         if (temp[k] != '0') {
            pos = k;
            break;
         }
      }
      for (int k = pos; k > 0; --k) {
         swap(temp[k], temp[k - 1]);
         ++cnt;
      }
      long long num = atoll(temp.c_str());
      if (num % 25 == 0)
         ans = min(ans, cnt);
      }
   }
   if (ans == INT_MAX)
      return -1;
   return ans;
}
int main(){
   int n = 5071;
   cout << "Minimum required moves: " << requiredMoves(n) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Minimum required moves: 4