36. Double-base Palindromes [10진수 및 2진수 모두 대칭수인 수 찾기]

​문제 (English)

The decimal number, $285=1001001001_{2}(binary)$, is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2. (Please note that the palindromic number, in either base, may not include leading zeros.)

 

Answer: 872187

문제 분석

---

285와 같이 앞으로 읽은 수와 뒤로 읽은 수가 같은 수를 '대칭수(Palindromes)'라고 한다. 285를 이진수로 나타내면 '1001001001'로, 이것도 앞으로 및 뒤로 읽었을 때 동일한 수이다. 이처럼 10진수일 때와 2진수일 때 모두 대칭수가 되는 수를 찾아서 더하라는 문제.

 

Project Euler 4번에서 이미 10진수일 때의 대칭수를 구하는 문제를 푼 바 있다. 이것을 2진수일 때도 대칭수가 되는지 알아낼 수 있으면 되겠다.

 

풀이 1 

---

10진수에 대해서 대칭수가 되는지 판별하는 코드는 아래와 같다. 앞서 Project Euler 4번 문제에서 푼바 있다. 

fn is_palindromes_10(num:usize) -> bool {
    if num % 10 == 0 {return false;}

    let mut n:usize = num;
    let mut rev:usize = 0;
    while n > 0 {
        rev = 10 * rev + n % 10;
        n /= 10;
    }    
    return num == rev;
}

 

2진수에 대한 대칭수가 되는지의 판단은, while 루프안에 있는 10 대신에 2를 넣어서 풀면 된다. 

 

그럼, 모든 진수에 대해서 대칭수가 되는지 판단하는 범용함수를 만들 수 있겠다.

//num:limit, b:base
fn is_palindromes(num:usize, b:usize) -> bool {
    if num % b == 0 {return false;}

    let mut n:usize = num;
    let mut rev:usize = 0;
    while n > 0 {
        rev = b * rev + n % b;
        n /= b;
    }    
    return num == rev;
}

 

이제, 백만 미만의 숫자에 대해 10진수에 대해서 대칭수, 그리고 이진수에 대해서 대칭수가 되는지를 판단하면 되겠다. 

fn solve(n:usize) -> usize {
    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if is_palindromes(i,10) && is_palindromes(i,2) {v.push(i);}       
    }
    println!("{:?}",v);
    return v.into_iter().sum();
}

 

풀이 2 

---

HackerRank에서는 10진수와 k진수에 대해 모두 대칭수가 되는 수를 찾으라고 변형되어 있다. 2진수 대신에 k진수의 경우만 고려하면 되기에, 위 풀이 1과 별반 다르지 않겠다.

#[test]
fn test1(){
    assert_eq!(25, solve1(10,2));    
    assert_eq!(1772, solve1(1000,2));
    assert_eq!(872187, solve1(1000000,2));
}

#[cfg(test)]
//n:limit, b:base
fn solve1(n:usize, b:usize) -> usize {
    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if is_palindromes(i,10) && is_palindromes(i,b) {v.push(i);}       
    }
    // println!("{:?}",v);
    return v.into_iter().sum();
}

 

총평

---

k진수에 대한 대칭수 판별 코드만 만들 수 있으면 쉽게 풀 수 있는 문제이다.

 

전체 소스코드

---

p36.rs 

#[test]
fn test(){
    assert_eq!(1772, solve(1000));
    assert_eq!(872187, solve(1000000));
}

#[cfg(test)]
fn solve(n:usize) -> usize {
    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if is_palindromes(i,10) && is_palindromes(i,2) {v.push(i);}       
    }
    println!("{:?}",v);
    return v.into_iter().sum();
}

#[cfg(test)]
//num:limit, b:base
fn is_palindromes(num:usize, b:usize) -> bool {
    if num % b == 0 {return false;}

    let mut n:usize = num;
    let mut rev:usize = 0;
    while n > 0 {
        rev = b * rev + n % b;
        n /= b;
    }    
    return num == rev;
}

#[cfg(test)]
fn is_palindromes_10(num:usize) -> bool {
    if num % 10 == 0 {return false;}

    let mut n:usize = num;
    let mut rev:usize = 0;
    while n > 0 {
        rev = 10 * rev + n % 10;
        n /= 10;
    }    
    return num == rev;
}

//------------------------
//HackerRank
#[test]
fn test1(){
    assert_eq!(25, solve1(10,2));    
    assert_eq!(1772, solve1(1000,2));
    assert_eq!(872187, solve1(1000000,2));
}

#[cfg(test)]
//n:limit, b:base
fn solve1(n:usize, b:usize) -> usize {
    let mut v:Vec<usize> = Vec::new();
    for i in 0..n {
        if is_palindromes(i,10) && is_palindromes(i,b) {v.push(i);}       
    }
    // println!("{:?}",v);
    return v.into_iter().sum();
}

 

끝