이 문제에서는 숫자가 주어지고 숫자에서 더 많은 숫자를 제거해야 합니다. 제거 후 생성된 새로운 숫자는 6으로 나누어 떨어지도록 합니다.
개념을 더 잘 배우기 위해 예를 들어 보겠습니다 −
Input : 1324 Output : 4
설명 − 4번째 숫자를 제거하면 6으로 나누어지는 132가 됩니다.
여기에 숫자가 주어지고 6으로 나누어 떨어지도록 숫자가 제거된 위치를 반환해야 합니다.
이 문제를 해결하기 위해 문제를 해결하는 논리를 만들려고 합니다. 이를 위해 우리는 숫자가 2와 3으로 나누어 떨어지면 6으로 나눌 수 있다는 지식을 사용할 것입니다.
숫자에서 숫자를 제거한 후 새로 생성된 숫자는 6의 배수, 즉 2와 3의 배수인지 확인합니다.
접근
숫자를 기반으로 숫자를 제거하여 생성된 숫자가 6의 배수인지 아닌지를 알 수 있습니다. 숫자의 마지막 숫자를 보면 두 가지 조건이 발생합니다.
마지막 숫자가 홀수인 경우
마지막 숫자가 홀수인 경우 가능한 유일한 방법은 마지막 숫자를 제거하는 것입니다. 그리고 새 숫자는 마지막 숫자 옆의 숫자가 짝수인 경우에만 6으로 나누어 떨어지지 않습니다. 그렇지 않으면 해결이 불가능합니다.
마지막 숫자가 짝수인 경우
마지막 숫자가 짝수이면 숫자를 3으로 나눈 나머지를 구해야 하며 이 숫자를 기반으로 제거할 수 있는 숫자를 확인할 수 있습니다.
숫자를 3으로 나눌 때 세 가지 경우 -
나머지는 1입니다 - 나눗셈의 나머지가 1이면 배열에서 숫자 1, 4, 7을 제거할 수 있습니다. 제거할 수 있는 숫자가 여러 개인 경우 제거 후 생성된 숫자가 가장 큰 숫자가 되도록 제거합니다.
나머지는 2입니다 - 나눗셈의 나머지가 2이면 배열에서 숫자 2, 5, 8을 제거할 수 있습니다. 제거할 수 있는 숫자가 여러 개인 경우 제거 후 형성된 숫자가 가장 큰 숫자가 되도록 제거합니다.
나머지는 3입니다. - 나눗셈의 나머지가 1이면 숫자 3, 6, 9 중 하나를 배열에서 제거할 수 있습니다. 제거할 수 있는 숫자가 여러 개인 경우 제거 후 형성된 숫자가 가장 큰 숫자가 되도록 제거합니다.
이를 바탕으로 몇 가지 문제를 해결하고 원하는 결과를 찾아봅시다 -
마지막 숫자가 홀수인 경우
1. 34241341
이 경우 제거할 수 있는 유일한 숫자는 마지막 위치에서 1이고 형성된 숫자는 6으로 나누어 떨어지는 3432134입니다. 따라서 제거된 1의 위치, 즉 8
을 반환합니다.2. 3214241
이 경우 제거할 수 있는 유일한 숫자는 마지막 위치에서 1이고 생성된 숫자는 341224입니다. 이는 6으로 나눌 수 없습니다. 따라서 -1을 반환합니다.
마지막 숫자가 짝수인 경우
1. 8097860
이 경우 숫자를 3으로 나누고 나머지가 2인 나머지를 찾아야 합니다. 따라서 나머지가 2인 경우 숫자에서 2, 5, 8을 제거할 수 있습니다. 따라서 위치 1과 5에서 8을 제거하여 숫자를 2로 나눌 수 있습니다. 첫 번째 위치에서 제거하면 더 작은 숫자가 반환되므로 5번째 위치에서 8을 제거합니다. 새로 형성된 숫자는 809760이며 6으로 나누어 떨어지므로 5를 반환합니다.
예시
이 논리를 기반으로 문제를 해결하는 프로그램을 만들 수 있습니다 -
#include <bits/stdc++.h>
using namespace std;
void isDivisibleBy6(string num){
int n = num.length();
int a[n];
int sum = 0;
for (int i = 0; i < n; i++) {
a[i] = num[i] - '0';
sum += a[i];
}
if (a[n - 1] % 2){
if ( (a[n - 2] % 2 != 0) || (sum - a[n - 1]) % 3 != 0) {
cout << "-1" << endl;
}
else {
cout << n << endl;
}
}
else {
int re = sum % 3;
int del = -1;
int flag = 0;
for (int i = 0; i < n - 1; i++) {
if ((a[i]) % 3 == re) {
if (a[i + 1] > a[i]) {
del = i;
flag = 1;
break;
}
else {
del = i;
}
}
}
if (flag == 0) {
if (a[n - 2] % 2 == 0 and re == a[n - 1] % 3)
del = n - 1;
}
if (del == -1)
cout << -1 << endl;
else {
cout << del + 1 << endl;
}
}
}
int main(){
string number = "343224152";
isDivisibleBy6(number);
return 0;
} 출력
5