문제 (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
문제 분석
크게 두 가지의 푸는 방법이 있다.
- 3자리의 두 수를 곱한 후, 이 값이 palindrome인지 판단하면서 답을 구하는 방법
- 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 |