본문 바로가기
Programming/Rust로 Euler 문제 풀이

004. Largest Palindrome Product (가장 큰 대칭수 찾기)

heejin_park 2024. 8. 12. 21:58
반응형

​문제 (English)

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

 

Answer: 906609

문제 분석

크게 두 가지의 푸는 방법이 있다. 

  1. 3자리의 두 수를 곱한 후, 이 값이 palindrome인지 판단하면서 답을 구하는 방법
  2. 3 자릿수와 그것을 뒤집어서 합해서 palindrome 수를 만들고, 이 수가 3자리 수의 곱이 되는지 판단하면서 구하는 방법

풀이 1 

100..=900까지의 2개 수를 곱하고, 이 수가 palindrome인지 판단하면서 답을 구한다.

1) a=100..=999까지 증가시키고,  b=100..=999까지 증가시키면서

2) p=ab

3) (p<n && is_palindromic(p) && p> max) 이면 max=p

 

palindrome인지 판단하는 is_palindrome 함수에서는, num을 reverse 하는 방법이 나온다. 원리는,

- 가장 오른편에 있는 1의 자릿수를 구하는 것은 n%10을 하면된다.

- 이 n%10한 값을 한 칸씩 왼쪽으로 옮기면 되는데, 이 때는 10을 곱하면 된다.

- 따라서, n > 0이 될 때까지 n /= 10을 해주면서, rev를 구하면 된다.

  while n > 0 {

      rev = 10 * rev + n % 10;

      n /= 10;

  }

 

소스는 아래와 같다.

#[test]
fn test(){
    
    assert_eq!(101101, find_palindrome(101110));
    assert_eq!(793397, find_palindrome(800000));

    let s = std::time::Instant::now();
    assert_eq!(906609, find_palindrome(906610));
    println!("test: {:?}", s.elapsed());
}

#[cfg(test)]
fn find_palindrome(n:u32) -> u32 {
    //1. find from [100..=999]
    let mut a:u32 = 100;
    let mut max:u32 = 1;    
    while a <= 999 {
        let mut b:u32 = 100;
        let mut p:u32;    
        while b<= 999 {
            p = a*b;
            if p <n && is_palindrome(p) && p>max { max = p; }
            b += 1;
        }
        a += 1;
    }
    return max;
}

#[cfg(test)]
fn is_palindrome(num:u32) -> bool {
    let mut n = num;
    let mut rev:u32 = 0;
    while n > 0 {
        rev = 10 * rev + n % 10;
        n /= 10;
    }
    return num == rev;
}

풀이 2 

풀이 1로도 hackerrank는 통과한다. 그래도, 좀 더 코드를 효율화해보자.

 

ab = ba 이기에, a<b인 경우에 대해서만 p=ab를 구하게 하면, 계산량이 줄어든다.

#[cfg(test)]
fn find_palindrome1(n:u32) -> u32 {
    //1. find from [100..=999]
    let mut a:u32 = 100;
    let mut max:u32 = 1;    
    while a <= 999 {
        let mut b:u32 = a;  // old: b=100
        let mut p:u32;    
        while b<= 999 {
            p = a*b;
            if p <n && is_palindrome(p) && p>max { max = p; }
            b += 1;
        }
        a += 1;
    }
    return max;
}

 

위 코드를 보면, while a<= 999 루프에서 b=a에서 시작해서 1씩 증가하도록 했다. 즉, a<=b의 경우만 고려한 것

 

좀  더 속도를 빠르게 할 수 있다.

a를 100에서 시작하게 했는데, 반대로 999에서 시작하면 더 빨리 찾을 수 있겠다. (어차피 palindrome이 되는 가장 큰 값을 찾는 것이기에)

 

#[cfg(test)]
fn find_palindrome2(n:u32) -> u32 {
    //1. find from [999..=100]
    let mut a:u32 = 999;
    let mut max:u32 = 1;    
    while a >= 100 {
        let mut b:u32 = 999;  
        let mut p:u32; 

        //만약 a=500이면, b=[999..=500]    
        while b >= a {
            p = a*b;
            if p <= max {break; }  //더이상 조사해볼 필요 없음. b/c 항상 더 작은 값이니.
            if p <n && is_palindrome(p) && p>max { max = p; }
            b -= 1;
        }
        a -= 1;
    }
    return max;
}

위 코드에서 p<= max이면 바로 break를 해버렸다. 왜냐면, while 루프를 돌아봐야 b를 계속 감소시키는 것이기에, p값은 항상 더 작아지기 때문에, 이미 구한 max보다는 항상 작다. 따라서, 루프에서 p <= max 되는 p를 만나면, 그냥 break 해버려도 된다.

풀이 3

풀이 2까지는 세 자리 a, b에 대해서 p=ab를 구하고, p가 palindrome인지를 확인하면서 답을 구했다.

 

이와 다르게, 아예 palindrome 되는 6자리 수를 구하고(세 자리 수의 곱의 최대는 6자리), 이 수가 두 개의 3자리 수의 곱이 되는지를 확인하는 방법으로 답을 구해보자.

 

어떤 n 값이 3자리 정수의 곱이 되는지는,

1) j = 999..=100에 대해 loop

2) (q,r) = n/j, n%j

3) (r==0 && q<=999) 이면, 만족하는 3자리 정수가 존재하는 것

 

소스코드는 아래와 같다. 

#[cfg(test)]
fn find_palindrome3(n:u32) -> u32 {
    //1. make palindromic num
    let mut x:u32 = n / 1000 + 1; //n보다 큰 수중 제일 작은 수    
    let mut max:u32 = 1;
    while x >= 100 {
        let y = rev_num(x);
        let p = x * 1000 + y;
        if p < n && is_product(p) {
            max = p;
            break;
        }
        x -= 1;
    }    
    return max;
}

#[cfg(test)]
fn rev_num(mut n:u32) -> u32 {   
    let mut rev:u32 = 0;
    while n > 0 {
        rev = 10 * rev + n % 10;
        n = n/10;
    }
    return rev;
}

#[cfg(test)]
fn is_product(n:u32) -> bool {
    //check the palindrome number of ii is whether the product of two integer    
    let mut ans:bool = false;
    for j in (100..=999).rev(){
        let (q,r):(u32,u32) = (n/j, n%j);                             
        if r==0 && q<=999{  //n = j * q, but must be q<max
            ans = true;
            break;
        }           
        if q > 999 {break; }  //n = j * q, if q>max -> j is too small so no need to continue 
    }
    return ans;
}

총평

전체 코드를 수행해 보면 풀이 3에 의한 코드가 수행속도가 제일 빠르다.

 

 

전체 소스코드

p4.rs 


#[test]
fn test(){
    
    assert_eq!(101101, find_palindrome(101110));
    assert_eq!(793397, find_palindrome(800000));

    let s = std::time::Instant::now();
    assert_eq!(906609, find_palindrome(906610));
    println!("test: {:?}", s.elapsed());
}

#[cfg(test)]
fn find_palindrome(n:u32) -> u32 {
    //1. find from [100..=999]
    let mut a:u32 = 100;
    let mut max:u32 = 1;    
    while a <= 999 {
        let mut b:u32 = 100;
        let mut p:u32;    
        while b<= 999 {
            p = a*b;
            if p <n && is_palindrome(p) && p>max { max = p; }
            b += 1;
        }
        a += 1;
    }
    return max;
}

#[cfg(test)]
fn is_palindrome(num:u32) -> bool {
    let mut n = num;
    let mut rev:u32 = 0;
    while n > 0 {
        rev = 10 * rev + n % 10;
        n /= 10;
    }
    return num == rev;
}

//------------------------------------
// a*b = b*a이기에, a<=b인 경우만 계산하게 함
#[test]
fn test1(){
    
    assert_eq!(101101, find_palindrome1(101110));
    assert_eq!(793397, find_palindrome1(800000));

    let s = std::time::Instant::now();
    assert_eq!(906609, find_palindrome1(906610));
    println!("test1: {:?}", s.elapsed());
}

#[cfg(test)]
fn find_palindrome1(n:u32) -> u32 {
    //1. find from [100..=999]
    let mut a:u32 = 100;
    let mut max:u32 = 1;    
    while a <= 999 {
        let mut b:u32 = a;  // old: b=100
        let mut p:u32;    
        while b<= 999 {
            p = a*b;
            if p <n && is_palindrome(p) && p>max { max = p; }
            b += 1;
        }
        a += 1;
    }
    return max;
}

//-------------------------------------------
// 100부터가 아닌 999부터 시작하게
#[test]
fn test2(){
    
    assert_eq!(101101, find_palindrome2(101110));
    assert_eq!(793397, find_palindrome2(800000));

    let s = std::time::Instant::now();
    assert_eq!(906609, find_palindrome2(906610));
    println!("test2: {:?}", s.elapsed());
}

#[cfg(test)]
fn find_palindrome2(n:u32) -> u32 {
    //1. find from [999..=100]
    let mut a:u32 = 999;
    let mut max:u32 = 1;    
    while a >= 100 {
        let mut b:u32 = 999;  
        let mut p:u32; 

        //만약 a=500이면, b=[999..=500]    
        while b >= a {
            p = a*b;
            if p <= max {break; }  //더이상 조사해볼 필요 없음. b/c 항상 더 작은 값이니.
            if p <n && is_palindrome(p) && p>max { max = p; }
            b -= 1;
        }
        a -= 1;
    }
    return max;
}

//-------------------------------------------
// a,b를 변화시키면서 p가 palindromic인지 확인하는 것이 아니라,
// palindromic되는 p를 먼저 구하고, 이게 a*b인지 확인
#[test]
fn test3(){
    
    assert_eq!(101101, find_palindrome3(101110));
    assert_eq!(793397, find_palindrome3(800000));

    let s = std::time::Instant::now();
    assert_eq!(906609, find_palindrome3(906610));
    println!("test3: {:?}", s.elapsed());
}

#[cfg(test)]
fn find_palindrome3(n:u32) -> u32 {
    //1. make palindromic num
    let mut x:u32 = n / 1000 + 1; //n보다 큰 수중 제일 작은 수    
    let mut max:u32 = 1;
    while x >= 100 {
        let y = rev_num(x);
        let p = x * 1000 + y;
        if p < n && is_product(p) {
            max = p;
            break;
        }
        x -= 1;
    }    
    return max;
}

#[cfg(test)]
fn rev_num(mut n:u32) -> u32 {   
    let mut rev:u32 = 0;
    while n > 0 {
        rev = 10 * rev + n % 10;
        n = n/10;
    }
    return rev;
}

#[cfg(test)]
fn is_product(n:u32) -> bool {
    //check the palindrome number of ii is whether the product of two integer    
    let mut ans:bool = false;
    for j in (100..=999).rev(){
        let (q,r):(u32,u32) = (n/j, n%j);                             
        if r==0 && q<=999{  //n = j * q, but must be q<max
            ans = true;
            break;
        }           
        if q > 999 {break; }  //n = j * q, if q>max -> j is too small so no need to continue 
    }
    return ans;
}

 

끝

반응형
저작자표시

'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글

006. Sum Square Difference ("제곱의 합"과 "합의 제곱"과의 차 구하기)  (0) 2024.08.13
005. Smallest Multiple (여러 수에 대한 최소공배수 구하기)  (0) 2024.08.13
003. Largest Prime Factor (어떤 수에 대한 가장 큰 소인수 구하기)  (0) 2024.08.12
002. Even Fibonacci Numbers (피보나치 수 중에서 짝수 구하기)  (0) 2024.08.12
001. Multiples of 3 or 5 (3과 5의 배수들의 합)  (0) 2024.08.12

'Programming/Rust로 Euler 문제 풀이' Related Articles

티스토리툴바