문제 (English)
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98=4/8, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, 30/50=3/5, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
Answer: 100
문제 분석
어떤 두 자리 수로 분자, 분모가 이루어진 분수에서, 두 자릿수 중에서 공통된 한 자리값을 제거했을 때도 원래의 분수값과 똑같이 되는 이상한 수가 있다. 예를 들어 49/98에서 분자, 분모에서 공통되는 값인 9를 제거하면 4/8이 되고, 이는 원래의 값인 49/98과 똑같다. 즉, 49/98=4/8
이렇게 두 자리 수에서 어떤 공통된 한자리를 빼도 원래의 분수값과 동일한 값이 되는 수를 찾으라는 문제.
이때 다음과 같은 경우는 제외한다.
- 공통된 값으로 0을 제외하는 것은 제외. 예를 들어 20/30에서 0을 제외하면 20/30 = 2/3이 되는데, 이러한 것은 당연한 것이기에, 찾으려는 이상한 수에는 포함시키지 않는다.
- 분자, 분모에 동일한 값인 경우도 제외. 즉, 45/45와 같은 경우는 제외
이러한 이상한 분수는 4개 있다고 하는데, 모두 1보다 작다고한다. 즉, 분자 <분모
이 4개 분수에 대해 분자끼리 곱한 것을 분자로, 분모끼리 곱한 값을 분모로 해서 어떤 분수를 만들었을 때, 이 분수를 기약분수로 만들었을 때 분모의 값을 구하시오.
문제에서 제일 마지막 문장의 해석이 어렵다.
If the product of these four fractions is given it its lowest common terms, find the value of denominator.
4개 분수를 곱하고, 나눌 수 있는 만큼 약분해서 기약분수로 만들고, 이때 분모의 값을 찾으라는 의미.
꽤 어려운 문제이다.
그래도 2자리 수 분수에 대해서는 그럭저럭 풀 수 있으나, HackerRank에서 3 자릿수, 4 자릿수에 대해서 해당되는 수를 찾으라는 문제는, 꽤나 어렵다.
풀이 1과 풀이 2에서는 2자리 수 분수에 대한 일반적인 풀이를 하고, 풀이 3에서는 HackerRank에서 요구되는 문제풀이를 한다.
풀이 1
가장 간단히 생각해 볼 수 있는 풀이 방법이다. 그냥 무작위로 두 자릿수 12~98까지 돌려서 조건에 맞는지 찾는 방법.
- 11부터 시작하지 않은 이유는, 가능한 경우가 없기 때문.
분자건 분모이건 한쪽이 11이면, 다른 쪽은 10의 자리에 1이 있거나, 1의 자리에 '1'이 있어야 한다. 즉, $(10+a)$ 혹은 $ (10a+1)$
분모에서 1의 자리가 1인 경우를 보면, 분자/분모에 있는 '1'을 제거해서 같아야 하기에,
$$ \frac{11}{10+a} = \frac{1}{a} $$
$$ 10+a = 11a $$
$$ a=1$$
즉, a=1인 경우니깐 11/11의 경우에만 해당하는 사항이기에, 11은 무조건 안된다. 1의 자리에 '1'이 있는 경우도 계산하면 동일
분자/분모에 있는 두 자릿수에서 공통된 값을 제거할 때는, 같은 자릿수에서 제거해서는 조건에 맞는 수를 찾을 수 없다. 분자에서 10의 자리의 수와 분모의 1의 자리 수 등 서로 다른 자릿수의 공통된 값을 제거해야 한다.
이유는, 분자의 값을 C, 분모의 값을 P라 하고, 분자의 각 자릿수의 값을 c1, c2, 분모에 있는 수를 p1, p2라고 하자.
예를 들어 49/98의 경우이면,
- C=39, P=98
- c1=3, c2=9
- p1=9, p2=8
10의 자릿수를 없애는 경우를 생각해 보자. 분자, 분모 모두 10의 자리에 공통된 수가 있는 경우
공통된 수를 n이라 하고, 분자에 남는 수를 c, 분모에 남는 수를 p라고 하자.
$$ \frac{C}{P} = \frac {10n+c}{10n+p}$$
10의 자리에 있는 n을 없애면 c/p가 되기에,
$$ \frac{10n+c}{10n+p} = \frac{c}{p}$$
$$ (10n+c)p = (10n+p)c$$
$$ 10np+cp = 10nc+cp$$
$$ 10n(p-c) = 0 \tag{1}$$
식 1에서 보면, n=0 혹은 p=c라야 수식을 만족한다.
n=0이면 trivial 한 경우이고, p=c라면 분자, 분모가 같은 값이여서 역시 trivial한 케이드다. 즉, 분자와 분모의 10의 자리에 있는 같은 값을 없애서, 조건을 만족시키는 값을 찾을 수는 없다.
동일한 원리로, 분자와 분모의 1의 자리의 값을 없애는 경우도, 조건을 만족시키는 값이 없다.
이제 알고리즘을 생각해 보면,
1) i = 11~98 까리 루프
2) j = i +1 ~ 98까지 루프 --> 왜냐면 i/j 형태를 만들 거고, 분수의 값이 1보다 작아야 하기에 항상 i <j라야 함
3) 의미 없는 경우의 수 제거
i == j의 경우 || i % 10==0 || j % 10 ==0
4) 분자와 분모의 서로 다른 자릿수에서 제거했을 때, 조건 만족시키는 값 찾기
4번을 구현할 때는,
만약, 분자의 1의 자리와, 분모의 10의 자릿수가 같은 경우라고 하면,
$$ \frac{C}{P} = \frac{10c1+c2}{10p1+p2}$$
여기서 c1==p1이고, 이 값을 제거. 따라서,
$$ \frac{C}{P} = \frac{c2}{p2}$$
$$ P \cdot c2 = C \cdot p1$$
즉, 원래의 분수함수와 값이 같은 것을, 실제 분수로 계산된 값을 비교하지 않고, 이처럼 곱셈의 비교로 전환하는 것이 좋다. 나눗셈의 경우 소숫점 끝자리에서 오차가 있을 수 있고 계산량도 곱셈보다 많기 때문.
작성된 코드는 아래와 같다.
#[cfg(test)]
fn get_set() -> HashSet<(usize, usize)>{
let mut set:HashSet<(usize,usize)> = HashSet::new();
for c in 12..=99{
for p in c+1..=98{
if c==p || c%10==0 || p%10==0 {continue;}
let c1:usize = c / 10; let c2:usize = c % 10;
let p1:usize = p / 10; let p2:usize = p % 10;
if (c1==p2 && p*c2 == c*p1) || (c2==p1 && p*c1==c*p2) {
set.insert((c,p));
}
}
}
return set;
}
이렇게 구해진 분수 4개는,
$$ \frac{16}{64}, \frac{26}{65}, \frac{19}{95}, \frac{49}{98}$$
구하라는 것은, 이 4개의 분수를 곱하고, 기약분수로 나타냈을 때의 분모 값이다.
4개의 분수를 곱한 값을 $\frac{C}{P}$라고 하고, G=GCD(C,P)라고 하면, 기약분수는 $\frac{C/G}{P/G}$이다. 분자와 분모를 최대공약수로 나눠주면 된다.
이렇게 짠 전체 코드는,
#[test]
fn test(){
//only for n=2, k=1
assert_eq!(100, solve());
}
#[cfg(test)]
fn solve() -> usize {
let set = get_set();
let mut nume_product = 1; let mut denume_product = 1;
for s in set{
nume_product *= s.0; denume_product *= s.1;
}
return denume_product / gcd(nume_product, denume_product);
}
#[cfg(test)]
//use the formula : gcd(a, b) = gcd(a, a%b)
fn gcd(mut a:usize, mut b:usize) -> usize{
let mut t: usize;
while b != 0 {
t = b; b = a % b; a = t;
}
return a;
}
#[cfg(test)]
fn get_set() -> HashSet<(usize, usize)>{
let mut set:HashSet<(usize,usize)> = HashSet::new();
for c in 12..=99{
for p in c+1..=98{
if c==p || c%10==0 || p%10==0 {continue;}
let c1:usize = c / 10; let c2:usize = c % 10;
let p1:usize = p / 10; let p2:usize = p % 10;
if (c1==p2 && p*c2 == c*p1) || (c2==p1 && p*c1==c*p2) {
set.insert((c,p));
}
}
}
return set;
}풀이 2
풀이 1보다 조금 더 빠르게 만들 수 있다.
- 풀이 1에서는 분자와 분모에서 같은 자리에 있는 공통 수를 빼는 것을 제외했는데, 분자의 10의 자리와 분모의 1의 자리의 공통 수를 빼는 것도 제외할 수 있다. 즉, 남는 것은 분자에서 1의자리와 분모에서 10의 자리의 공통수를 빼는 경우만 조건을 만족시키는 것
- 풀이1에서는 두 자릿수에 해당하는 경우의 수를 12~98까지에 대해 분자와 분모에 대해 고려를 했는데, 분자의 10의 자리에 1~9까지, 분모의 1의 자리에 1~9까지, 그리고 공통수 1~9까지로 하면, 풀이 1보다 더 적은 경우의 수에 대해서 조사하게 된다.
분자의 10의 자리와 분모의 1의 자리에 공통수가 있는 경우, 조건을 만족하지 못함을 알아보자.
$$ \frac{10n+c}{10p+n} = \frac{c}{p}$$
$$ 10np+cp = 10cp+nc$$
$$ 10p(n-c) = c(n-p) \tag{2}$$
식 2에서,
1)if (n != c), $1 < \frac{10(n-c)}{n-p} = \frac {c}{p} < 1 \rightarrow (X)$
2)if (n == c), $c=0 or n==p \rightarrow (X) $
n != c의 경우, $\frac{10(n-c)}{n-p}$는 1보다 크다. 근데 이 값과 같다는 $\frac{c}{p}$는 분수의 값이 1보다 작다는 문제의 조건에서 주어진 바와 같이 1보다 작기에 모순
n==c의 경우도, c==0의 경우 n도 0이 되어 말이 안 되고, n==p의 경우도 n = p = c가 되어야기에 말이 안 된다.
즉, 분자의 10의 자리와 분모의 1의 자리에 공통수가 올 수 없다.
이제, 남아있는 하나의 경우의 수는, 분자의 1의 자리와 분모의 10의 자리에 공통수가 있는 경우 한 가지뿐
$$ \frac{10c+n}{10n+p} =\frac {c}{p}$$
$$ (10c+n)p = (10n+p)c$$
$$ 10cp+np = 10nc + cp$$
$$ 10c(p-n) = p(c-n) \tag{3}$$
식 3에서,
1)if p=n, $0 = p(c-n) \rightarrow p=0 || c=n$
2)if p!=n, $ \frac{10c}{p} = \frac{c-n}{p-n} \tag {4}$
만약 p==n이면, p=0 혹은 c=n이라야 해서, 말이 안 된다.
만약 p!=n이면 식 4를 만족하면 되고 이때 c < p < n 이 된다.
c <p <n이 되는 이유는, 식 4에서, $1 < \frac{10c}{p}$이기에 $frac{c-n}{p-n}$도 1보다 커야 하고, 따라서 $|c-n| > |p-n|$이라야 한다. 여기서, 문제 조건에 의해서 c < p 이기에 c < p < n이 되어야 한다.
왜냐하면, c <p인데, c에서 어떤 값 n을 뺀 절댓값이 |c-n|이 |p-n|보다 커지려면 n과 p와의 거리보다, n과 c의 거리가 더 길어져야 하기 때문.
위 설명에 부합하게 짠 코드는 아래와 같다. 코드가 좀 더 간략해졌다.
#[cfg(test)]
fn get_set2() -> HashSet<(usize, usize)>{
let mut set:HashSet<(usize,usize)> = HashSet::new();
for c in 1..=9 {
for p in c+1..=9 {
for n in p+1..=9 {
if 10*c*(n-p) == p*(n-c) {set.insert((c,p));}
}
}
}
return set;
}
풀이 3
풀이 1과 풀이 2는 두 자리 수중에서 한 개 숫자를 소거하는 경우였다. 변수 n과 k로 얘기하면, n=2, k=1의 경우
HackerRank에서는 $2 \leq n \leq 4$, $1 \leq k \leq n-1$ 이다.
n=3 이상의 경우, 풀이 1과 풀이 2와 같이 각 자릿수에 들어가는 1~9까지의 수를 가정해서, 각 자릿수의 어떤 값이 삭제될 수 있는지 등으로 풀기 힘들다. 실제 조합으로 경우의 수를 만들고, 하나씩 빼보면서 조건에 맞는지를 체크하는 수밖에 없다.
다양한 풀이 방법을 생각할 수 있겠는데, 필자는 아래와 같이 풀었다.
1) n, k에 따라 대상이 되는 후보 수들을 뽑는다. 이때, 해당 수에 대해 공통으로 뽑힐 수(common), 남겨지는 수(remained)에 따라 후보 수들이 뽑힌다.
2) 앞에서 뽑은 후보 수들에서 common이 같은 후보 수들에 대해서, remained만의 분수값과 원래의 분수값이 같은지를 체크하면서 답을 찾는다.
n=2, k=1의 경우를 보자.
후보가 되는 수는 2자리 수로 12~98까지의 수이다.
여기서 한 자리 공통 수를 뽑아낼 건데, 1을 공통으로 했을 때, (remaind, origin)에 해당하는 값은 다음과 같다.
[1]: [(2, 12), (3, 13), (4, 14), (5, 15), (6, 16), (7, 17), (8, 18), (9, 19), (2, 21), (3, 31), (4, 41), (5, 51), (6, 61), (7, 71), (8, 81), (9, 91)]
만약 n=3, k=2의 경우, common=[1,2]의 경우는,
[1, 2]: {(6, 621), (2, 212), (3, 213), (7, 127), (7, 721), (6, 126), (1, 112), (5, 152), (4, 214), (7, 217), (3, 321), (2, 221), (6, 612), (2, 122), (4, 142), (3, 312), (8, 812), (7, 271), (4, 241), (9, 219), (9, 129), (5, 251), (8, 218), (8, 821), (1, 121), (3, 231), (8, 281), (4, 412), (9, 192), (5, 125), (8, 128), (6, 162), (8, 182), (3, 132), (1, 211), (7, 172), (9, 291), (6, 261), (3, 123), (5, 512), (4, 124), (5, 215), (6, 216), (7, 712), (4, 421), (9, 912), (5, 521), (9, 921)}
이 값을 뽑아내는 방법은,
1) common은 한 자리이기에, 두 자리 수인 후보수에서 1개를 뽑아내는 조합이다. 만약 n자리 수에서 k를 뽑아내는 거면 nCk와 같이 조합(Combination)으로 뽑아내는 거다. 예를 들어 n=3, k=2의 경우, "123"에 대해서는 common이 {[1,2], [1,3], [2,3]|과 같이 3개 있을 수 있다. DFS이용한 조합(Combinatoin) 구현하는 코드를 참조해서 구현할 수 있겠다.
2) HashMap을 쓰고, 이 HashMap의 키로 common을 쓰고, 이 키에 대한 value로는 (remained, origin_num)으로 하면, 같은 common에 대한 수들을 모을 수 있다.
이렇게 작성된 코드가 아래와 같다.
#[test]
fn test2(){
// assert_eq!((110,322), solve2(2,1));
// assert_eq!((77262, 163829), solve2(3,1));
assert_eq!((7429 , 17305), solve2(3,2));
// assert_eq!((12999936 , 28131911), solve2(4,1));
// assert_eq!((3571225 , 7153900), solve2(4,2));
// assert_eq!((255983 , 467405), solve2(4,3));
}
#[cfg(test)]
fn solve2(n:usize, k:usize) -> (usize, usize) {
//1. n, k에 따라 후보가 되는 수 집합 생성-> [common] : {(remained_num, origin_num), ...}
let mut tgt:HashMap<Vec<usize>, HashSet<(usize,usize)> > = HashMap::new(); //[common]: (remained, original_num)
let (s,e) = match n {2 => (12,98), 3 => (101,998), 4 => (1001,9998), _ => (0,0),};
for i in s..=e {
if is_usable(i, n) { get_combi_pair2(i, n, k, &mut tgt); }
}
// println!("tgt:{:?}",tgt);
//2. check for all target_list whether meet for the condition for Child/Parent
// - condition: C_common == P_common && C/P == C_r / P_r
let mut ans_h:HashSet<(usize,usize)> = HashSet::new(); // (child, parent)
for v in tgt.values() { // [(remainded, num), ( ), ...]
for i in v{
for j in v {
if i==j || i.0 >= j.0 {continue;} //same or remaind_child >= remainde_parent
let c = i.1; let p = j.1;
if c >= p {continue;}
if c * j.0 == p * i.0 { ans_h.insert((c,p));}
}
}
}
// println!("ans_h: {:?}", ans_h);
return get_sum(ans_h);
}
#[cfg(test)]
// {[1,2,3], [1,2,5]} n=3 k=2 --> (common, remained, origin)
// [1,2] : [([3],123), ([5],123)]
fn get_combi_pair2(num:usize, n:usize, r:usize, output:&mut HashMap<Vec<usize>, HashSet<(usize, usize)>>){
let input:Vec<usize> = num2digit(num);
let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
let mut buf:Vec<usize> = vec![0; n];
let mut used:Vec<bool> = vec![false; n];
for i in (0..n).rev() { s.push((0,i)); }
while s.len() > 0 {
let node = s.pop().unwrap(); // (depth, value)
let d = node.0; let v = node.1;
buf[d] = v;
if d == (r-1) {
let mut common = vec![0;r];
for i in 0..r { common[i] = input[buf[i]]; }
if is_contain_zero(&common) {continue;}
let mut remained:Vec<usize> = Vec::new();
let mut j = 0;
for i in 0..n {
if j < n && buf[j] == i {
j += 1; continue;
}
remained.push(input[i]);
}
let remained_num = digit2num(&remained);
if remained_num == 0 {continue;} //if 0 -> no meaning
common.sort();
if output.contains_key(&common) {
let mut v:HashSet<(usize,usize)> = output[&common].clone();
v.insert((remained_num, digit2num(&input)));
output.insert(common, v);
}else {
let tmp_set:HashSet<(usize,usize)> = HashSet::from([(remained_num, digit2num(&input))]);
output.insert(common, tmp_set);
}
continue;
}
used[v] = true;
for i in ((v+1)..n).rev(){
if used[i] {continue;}
s.push((d+1, i));
}
used[v] = false;
}
}
#[cfg(test)]
fn is_contain_zero(list:&Vec<usize>) -> bool {
for i in list { if *i == 0 {return true;} }
return false;
}
#[cfg(test)]
//123 -> true, 222 -> false, 200 -> false
fn is_usable(num:usize, n:usize) -> bool {
let (d1,d2) = match n {2 => (10,11), 3 => (100,111), 4 => (1000,1111), _ => (1,1,) };
if num % d1 == 0 || num % d2 == 0 {return false;}
return true;
}
#[cfg(test)]
fn is_same_element(a:&Vec<usize>, b:&Vec<usize>) -> bool {
// return b.iter().all(|item| a.contains(item));
if a.len() != b.len() {return false;}
let mut aa = a.clone(); aa.sort();
let mut bb = b.clone(); bb.sort();
for i in 0..aa.len(){
if aa[i] != bb[i] {return false;}
}
return true;
}
#[cfg(test)]
fn get_sum(h:HashSet<(usize,usize)>) -> (usize,usize){
let mut sum1:usize = 0; let mut sum2:usize = 0;
for t in h {
sum1 += t.0; sum2 += t.1;
}
return (sum1,sum2);
}
#[cfg(test)]
// 123 -> [1,2,3]
fn num2digit(a:usize) -> Vec<usize> {
let mut v:Vec<usize> = Vec::new();
let mut n = a;
while n > 0 {
v.push(n%10);
n /= 10;
}
v.reverse();
return v;
}
#[cfg(test)]
//[1,2,3] -> 123
fn digit2num(buf:&Vec<usize>) -> usize {
let mut v = buf.clone();
v.reverse();
let mut d = 1;
let mut n = 0;
for i in 0..v.len(){
n += v[i] * d;
d *= 10;
}
return n;
}총평
n=2일 때는 2자리 수에 대한 문제로, 수학 문제라 할 수 있고, n=3 이상일 때는 그냥 프로그래밍 문제이다.
그리고, n=4, k=1 일 때 가장 많은 경우의 수가 발생하는데, 약 $10^9$ 번 조건에 맞는 분수인지 확인해야 하고, 이렇게 하는데 약 2.5초가 소요되 된다.
꽤 효율적으로 코드를 짜도 이 정도이니, n=5 이상에 대해서는 수십 초 이상이 소요될 것으로 보인다.
n=3 이상의 경우에 대해서는 조합(Combination) 문제로, 여기서는 스택을 이용한 DFS형태의 구조로 '조합' 원소를 추출했다. 재귀호출로 구현했으면 속도는 더 느려졌을 것이다.
조합(Combination)에 대한 구현을 어떻게 하는지는 별도의 페이지에 상세 설명해놨으니 참조.
여하튼, 어려운 문제이다. HackerRank에서 1~32번까지의 문제는 난도가 '극하' 혹은 '하'라고 보면, 이 문제는 '중상' 정도의 난이도가 있는 문제.
전체 소스코드
p33.rs
#[test]
fn test(){
//only for n=2, k=1
assert_eq!(100, solve());
}
#[cfg(test)]
fn solve() -> usize {
let set = get_set();
let mut nume_product = 1; let mut denume_product = 1;
for s in set{
nume_product *= s.0; denume_product *= s.1;
}
return denume_product / gcd(nume_product, denume_product);
}
#[cfg(test)]
//use the formula : gcd(a, b) = gcd(a, a%b)
fn gcd(mut a:usize, mut b:usize) -> usize{
let mut t: usize;
while b != 0 {
t = b; b = a % b; a = t;
}
return a;
}
#[cfg(test)]
fn get_set() -> HashSet<(usize, usize)>{
let mut set:HashSet<(usize,usize)> = HashSet::new();
for c in 12..=99{
for p in c+1..=98{
if c==p || c%10==0 || p%10==0 {continue;}
let c1:usize = c / 10; let c2:usize = c % 10;
let p1:usize = p / 10; let p2:usize = p % 10;
if (c1==p2 && p*c2 == c*p1) || (c2==p1 && p*c1==c*p2) {
set.insert((c,p));
}
}
}
return set;
}
#[cfg(test)]
fn get_set2() -> HashSet<(usize, usize)>{
let mut set:HashSet<(usize,usize)> = HashSet::new();
for c in 1..=9 {
for p in c+1..=9 {
for n in p+1..=9 {
if 10*c*(n-p) == p*(n-c) {set.insert((c,p));}
}
}
}
return set;
}
//-----------------------------------------------
use std::collections::{HashSet,HashMap};
#[test]
fn test1(){
// assert_eq!((110,322), solve1(2,1));
assert_eq!((77262, 163829), solve1(3,1));
// assert_eq!((7429 , 17305), solve1(3,2));
// assert_eq!((12999936 , 28131911), solve1(4,1));
// assert_eq!((3571225 , 7153900), solve1(4,2));
// assert_eq!((255983 , 467405), solve1(4,3));
}
#[cfg(test)]
fn solve1(n:usize, k:usize) -> (usize, usize) {
let (s,e) = match n {2 => (12,98), 3 => (101,998), 4 => (1001,9998), _ => (0,0),};
let mut tgt:Vec<(Vec<usize>,usize,usize)> = Vec::new();
for i in s..=e {
if is_usable(i, n) {
get_combi_pair(i, n, k, &mut tgt);
}
}
// println!("tgt: {:?}",tgt);
//3. check for all target_list whether meet for the condition for Child/Parent
// - condition: C_common == P_common && C/P == C_r / P_r
let mut ans_h:HashSet<(usize,usize)> = HashSet::new(); // (child, parent)
for i in 0..tgt.len(){
for j in i+1..tgt.len(){
let c = tgt[i].2; let p = tgt[j].2;
if c == p {continue;}
if !is_same_element(&tgt[i].0, &tgt[j].0) {continue;}
//let c_r = digit2num(&tgt[i].1); let p_r = digit2num(&tgt[j].1);
let c_r = tgt[i].1; let p_r = &tgt[j].1;
if c * p_r == p * c_r { // c/p == tgt[i].1 / tgt[j].1
ans_h.insert((c,p));
}
}
}
// println!("ans_h: {:?}", ans_h);
return get_sum(ans_h);
}
#[cfg(test)]
// [1,2,3] n=3 k=2 --> ([common],remained, origin)
// ([1,2],3,123) ([1,3],2,123) ([2,3],1,123)
// [1,2,3] n=3 k=1
// ([1],23,123) ([2],13,123) ([3],12,123)
fn get_combi_pair(num:usize, n:usize, r:usize, output:&mut Vec<(Vec<usize>, usize, usize)>){
let input:Vec<usize> = num2digit(num);
let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
let mut buf:Vec<usize> = vec![0; n];
let mut used:Vec<bool> = vec![false; n];
for i in (0..n).rev() { s.push((0,i)); }
while s.len() > 0 {
let node = s.pop().unwrap(); // (depth, value)
let d = node.0; let v = node.1;
buf[d] = v;
if d == (r-1) {
let mut common = vec![0;r];
for i in 0..r { common[i] = input[buf[i]]; }
if is_contain_zero(&common) {continue;}
let mut remained:Vec<usize> = Vec::new();
let mut j = 0;
for i in 0..n {
if j < n && buf[j] == i {
j += 1; continue;
}
remained.push(input[i]);
}
let remainded_num = digit2num(&remained);
if remainded_num == 0 {continue;} //if 0 -> no meaning
let tmp = (common, remainded_num, digit2num(&input));
if !output.contains(&tmp) { output.push(tmp); }
continue;
}
used[v] = true;
for i in ((v+1)..n).rev(){
if used[i] {continue;}
s.push((d+1, i));
}
used[v] = false;
}
}
#[cfg(test)]
fn is_contain_zero(list:&Vec<usize>) -> bool {
for i in list { if *i == 0 {return true;} }
return false;
}
#[cfg(test)]
//123 -> true, 222 -> false, 200 -> false
fn is_usable(num:usize, n:usize) -> bool {
let (d1,d2) = match n {2 => (10,11), 3 => (100,111), 4 => (1000,1111), _ => (1,1,) };
if num % d1 == 0 || num % d2 == 0 {return false;}
return true;
}
#[cfg(test)]
fn is_same_element(a:&Vec<usize>, b:&Vec<usize>) -> bool {
// return b.iter().all(|item| a.contains(item));
if a.len() != b.len() {return false;}
let mut aa = a.clone(); aa.sort();
let mut bb = b.clone(); bb.sort();
for i in 0..aa.len(){
if aa[i] != bb[i] {return false;}
}
return true;
}
#[cfg(test)]
fn get_sum(h:HashSet<(usize,usize)>) -> (usize,usize){
let mut sum1:usize = 0; let mut sum2:usize = 0;
for t in h {
sum1 += t.0; sum2 += t.1;
}
return (sum1,sum2);
}
#[cfg(test)]
// 123 -> [1,2,3]
fn num2digit(a:usize) -> Vec<usize> {
let mut v:Vec<usize> = Vec::new();
let mut n = a;
while n > 0 {
v.push(n%10);
n /= 10;
}
v.reverse();
return v;
}
#[cfg(test)]
//[1,2,3] -> 123
fn digit2num(buf:&Vec<usize>) -> usize {
let mut v = buf.clone();
v.reverse();
let mut d = 1;
let mut n = 0;
for i in 0..v.len(){
n += v[i] * d;
d *= 10;
}
return n;
}
//---------------------------------
#[test]
fn test2(){
// assert_eq!((110,322), solve2(2,1));
// assert_eq!((77262, 163829), solve2(3,1));
// assert_eq!((7429 , 17305), solve2(3,2));
assert_eq!((12999936 , 28131911), solve2(4,1));
// assert_eq!((3571225 , 7153900), solve2(4,2));
// assert_eq!((255983 , 467405), solve2(4,3));
}
#[cfg(test)]
fn solve2(n:usize, k:usize) -> (usize, usize) {
//1. n, k에 따라 후보가 되는 수 집합 생성-> [common] : {(remained_num, origin_num), ...}
let mut tgt:HashMap<Vec<usize>, HashSet<(usize,usize)> > = HashMap::new(); //[common]: (remained, original_num)
let (s,e) = match n {2 => (12,98), 3 => (101,998), 4 => (1001,9998), _ => (0,0),};
for i in s..=e {
if is_usable(i, n) { get_combi_pair2(i, n, k, &mut tgt); }
}
// println!("tgt:{:?}",tgt.len());
//2. check for all target_list whether meet for the condition for Child/Parent
// - condition: C_common == P_common && C/P == C_r / P_r
let mut ans_h:HashSet<(usize,usize)> = HashSet::new(); // (child, parent)
for v in tgt.values() { // [(remainded, num), ( ), ...]
for i in v{
for j in v {
if i==j || i.0 >= j.0 {continue;} //same or remaind_child >= remainde_parent
let c = i.1; let p = j.1;
if c >= p {continue;}
if c * j.0 == p * i.0 { ans_h.insert((c,p));}
}
}
}
// println!("ans_h: {:?}", ans_h);
return get_sum(ans_h);
}
#[cfg(test)]
// {[1,2,3], [1,2,5]} n=3 k=2 --> (common, remained, origin)
// [1,2] : [([3],123), ([5],123)]
fn get_combi_pair2(num:usize, n:usize, r:usize, output:&mut HashMap<Vec<usize>, HashSet<(usize, usize)>>){
let input:Vec<usize> = num2digit(num);
let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
let mut buf:Vec<usize> = vec![0; n];
let mut used:Vec<bool> = vec![false; n];
for i in (0..n).rev() { s.push((0,i)); }
while s.len() > 0 {
let node = s.pop().unwrap(); // (depth, value)
let d = node.0; let v = node.1;
buf[d] = v;
if d == (r-1) {
let mut common = vec![0;r];
for i in 0..r { common[i] = input[buf[i]]; }
if is_contain_zero(&common) {continue;}
let mut remained:Vec<usize> = Vec::new();
let mut j = 0;
for i in 0..n {
if j < n && buf[j] == i {
j += 1; continue;
}
remained.push(input[i]);
}
let remained_num = digit2num(&remained);
if remained_num == 0 {continue;} //if 0 -> no meaning
common.sort();
if output.contains_key(&common) {
let mut v:HashSet<(usize,usize)> = output[&common].clone();
v.insert((remained_num, digit2num(&input)));
output.insert(common, v);
}else {
let tmp_set:HashSet<(usize,usize)> = HashSet::from([(remained_num, digit2num(&input))]);
output.insert(common, tmp_set);
}
continue;
}
used[v] = true;
for i in ((v+1)..n).rev(){
if used[i] {continue;}
s.push((d+1, i));
}
used[v] = false;
}
}
끝
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
| 35. Circular Primes [순환해도 소수가 되는 수 찾기] (0) | 2024.10.09 |
|---|---|
| 34. Digit Factorials [각 자릿수의 팩토리얼의 합과 원래 값이 같은 수 찾기] (0) | 2024.10.08 |
| 순열, 조합 - Permutation, Combination (0) | 2024.09.29 |
| 032. Pandigital Products [두 수의 곱이 Pandigital이 되는 수 찾기] (1) | 2024.09.11 |
| 031. Coin Sums [금액에 대해 영국 동전으로 만들 수 있는 조합 개수 찾기] (1) | 2024.09.09 |
