38. Pandigital Multiples [어떤 수에 1,2,...n을 차례로 곱한 값을 Concat했을 때 1~9까지 수 전체가되는 수 찾기]

​문제 (English)

Take the number 192 and multiply it by each of 1, 2, and 3:

$$ 192 \times 1 = 192$$

$$ 192 \times 2 = 384$$

$$ 192 \times 3 = 576$$

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and $(1,2,3)$.

 

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of $9$ and $(1,2,3,4,5)$.

 

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with $1,2,...,n$ where n > 1?

 

문제 분석

---

어떤 수 $x$에다가 1,2,...,n을 차례로 곱한 후, 곱한 결과를 문자열처럼 합쳤을 때, 1~9까지의 모든 수가 중복되지 않고 모두 포함되어 있을 때, 이 1~9까지의 포함된 수를 1 to 9 pandigital이라고 한다. 가장 큰 1 to 9 pandigital 수를 구하라.

이때, 곱하게 되는 수는 1,2,..., n인데, n > 1보다 크기에, 최소한 1과 2를 포함해서 곱한 후 구해야 한다. 

 

예를 들어 $x=123456789$는 답이 안된다. 왜냐면 $ 123456789 \times (1) $은 pandigital이 되긴 하지만 n > 1이라는 조건을 만족시키지 못하기 때문.

 

예제에서 주어진 $x=192$는 조건을 만족한다. 그러나, 이 값이 제일 큰 pandigital을 만들어내는지는 모른다. $x$의 값을 더 증가시키면서 조건에 맞는 값이 있는지 확인해봐야 한다.

 

주의할 것은, $x$ 값을 출력하라는 것이 아니고, pandigital 값을 출력하는 것.

 

풀이 1 

---

제일 큰 pandigital 값을 찾으라고 했기에, $x$에 대해서 가능한 제일 큰 수에서부터 감소시키면서 찾으면 되겠다.

그렇다면 가장 큰 $x$는 어느 정도일까?

 

$x$가 5자리 수라고 생각해 보자. 5자리에서 가장 작은 값은 10000이다.  그렇다면,

$$ 10000 \times 1 = 10000 $$

$$ 10000 \times 2 = 20000 $$

 

$x=10000$을 예로 든것은, 이 값이 pandigital을 생성할 수 있어서는 아니고, 결괏값의 자릿수를 가늠하기 위해서 사용한 것이다. 위와 같이, 가장 작은 5자리 수를 1과 2를 곱해서 pandigital을 만들면 10자리 수가 생성된다. 

원하는 것은 1~9까지의 pandigital 수이기에 9 자리라야 한다. 즉, $x$는 5자리 수는 안된다.

 

만약 4자리 수이면, 1과 2를 곱해서 만들면 8자리 혹은 9자리 수가 된다.  

5000 보다 큰 수일 때부터 9자리 수가 된다. 

즉, $x$는 5001부터 9999까지 범위안에 있다. 

 

좀 더 세밀하게 보면, 5123부터 9876사이에 있다. $x \times 1 = x$값이 pandigital의 맨 앞자리를 차지하기에, $x$ 값에 중복된 수가 들어가 있으면 안 되기 때문에, 5001보다 크면서 중복이 없는 가장 작은 값은 5123이고, 9999보다 작으면서 중복이 없는 가장 큰 수는 9876이기 때문.

pandigital 값이 가장 큰 값을 찾는 것은, 최대가되는 $x$를 구하는 것과 똑같은 말이다. 왜냐면, pandigital값이 제일 크려면 제일 앞자리부터 제일 커야 하는데, pandigital의 가장 앞 값은 $x \times 1=x$이기 때문.

 

따라서, $x=9876$부터 $5123$까지 감소시키면서 $1,2,...9$까지 곱해가면서 pandigital이 만들어지는지 확인하면 되겠다.

 

fn solve() -> String{
    for i in (5123..=9876).rev(){   
        let mut t:Vec<bool> = vec![false;10]; t[0] = true;
        let mut pan:Vec<usize> = Vec::new();
        for j in 1..=9 {
            let p = i*j; pan.push(p);
            if insert_digit(p, &mut t) == false {break;}
            if check_pan(&t) {return concat_num(&pan);}
        }
    }
    return "0".to_string();
}

 

위 코드에서 insert_digit 함수와 check_pan, concat_num 함수를 만들어서 사용했다. 

 

insert_digit 함수

pandigital이 되는지 확인하는 여러가지 방법을 생각할 수 있겠다.

여기서는, 크기가 10인 배열을 만들고, 거기서 1~9 자리에 값을 채우는 방식으로 pandigital이 되는지 확인하려 한다. 

 

 

$x$에 1,2,..을 곱해가면서 배열에 체크한다. $192 \times 1 = 192$의 경우 1번, 9번, 2번째 배열값을 체크한다. 

체크하려는데 이미 체크되어 있다면 중복이기에, 이 경우 해당 $x$는 pandigital을 만들 수 없는 값이어서 제외한다.

 

이렇게 하는 함수가 insert_digit 함수이다.

fn insert_digit(n:usize, arr:&mut Vec<bool>) -> bool {
    let digit_arr:Vec<usize> = to_digit(n);
    for i in digit_arr {
        if i >= arr.len() || arr[i] {return false;}
        arr[i] = true;
    }
    return true;
}

fn to_digit(mut n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    while n > 0 {
        v.push(n % 10);  n /= 10;
    }
    return v;
}

• insert_digit 함수에서, 배열 내 위치에 이미 체크되어 있는지를 확인할 때 $ i \le arr.len() || arr[i] $ 와 같이 i의 값도 체크했다. i >= arr.len()을 한 것은, "9 pandigital"의 경우 arr의 크기를 10으로 해서 사용할 것이기에 i >= arr.len() 이 되는 경우는 발생하지 않으나, HackerRank 문제에서와 같이 "8 pandigital"을 구하는 문제의 경우 arr의 크기를 9로 해서 사용할 것이기에, i >= arr.len()을 넣어서 "8 pandigital"에 대해서도 대응이 가능하도록 한 것임
• i값은 $x$의 각 자릿수이기에 0~9까지의 값이다. 따라서 $i=0$이라는 것은 $x$의 값에 0이 들어 있는 것이어서 pandigital을 만들지 못할 수이다. 따라서, insert_digit에 파라미터로 전달되는 arr 배열의 arr[0]=true로 이미 설정된 후 호출돼야 한다.  
• to_digit는 숫자를 각 자릿수를 나타내는 배열로 바꾸는 함수이다. 

배열이라고 설명해 놓고 실제 코드에서는 벡터를 사용한 것을 많이 볼 수 있을 것이다.

이는, 필자가, 배열을 사용할 수 있는 것도 벡터로 구현하는 것을 선호하기 때문이다. 

그냥 배열이라고 설명해도, 벡터로 구현될 것으로 생각하면 된다.

 

check_pan 함수

1~9까지가 체크된 배열에 대해서 pandigital이 되는지를 판별하는 함수이다. 배열의 인덱스 1~9까지가 모두 true로 되어 있으면 pandigital이고, 하나라도 false 이면 pandigital이 아니다. 

fn check_pan(arr:&Vec<bool>) -> bool {
    for b in arr {
        if *b == false {return false;}
    }
    return true;
}

 

concat_num 함수

$x$에 1,2,...,n 까지가 각각 곱해진 결괏값을 가지고 있는 배열을 가지고, 각 값을 합치는 함수이다. 

정수형이기에 합쳐진 결과도 정수형으로 만들 수도 있으나, 그럴 경우 그 수에 대한 자릿수에 해당하는 10의 지수승을 곱하면서 합쳐야 해서, 그냥 숫자를 문자열로 변환시키고, 그 문자열에 그 다음 수의 문자열을 합치는 형태로 코드를 짰다.

fn concat_num(pan:&Vec<usize>) -> String{
    let mut s:String = String::new();
    for i in pan {       
        s.push_str((*i).to_string().as_str());       
    }
    return s;
}

• 어떤 수 $n$을 String으로 변환하는 것은 n.to_string() 함수이다. String 타입이 만들어진다.
• String에서 다른 String을 바로 합치는 함수는 없다. 그러나 str을 합치는 push_str 함수는 있기에, 숫자에서 String으로 변환된 것을 다시 as_str()을 이용해서 str 타입으로 변환시켜서 push_str 했다.
  s.push_str((*i) .to_string().as_str());
• concat_num 함수의 파라미터로 전달되는 pan은 참조형이기에, for i in pan에서 i는 참조형 값이다. 따라서, i.to_string()이 아니라 (*i).to_string()이라야 한다.

 

이렇게 작성된 풀이 1 전체 코드는 아래와 같다.

결괏값은 932718654이고, 이 수는 $x=9327$의 경우에 생성된 pandigital 값이다.

#[test]
fn test(){
    assert_eq!("932718654".to_string(), solve());
}

#[cfg(test)]
fn solve() -> String{
    for i in (5123..=9876).rev(){   
        let mut t:Vec<bool> = vec![false;10]; t[0] = true;
        let mut pan:Vec<usize> = Vec::new();
        for j in 1..=9 {
            let p = i*j; pan.push(p);
            if insert_digit(p, &mut t) == false {break;}
            if check_pan(&t) {return concat_num(&pan);}
        }
    }
    return "0".to_string();
}

#[cfg(test)]
fn insert_digit(n:usize, arr:&mut Vec<bool>) -> bool {
    let digit_arr:Vec<usize> = to_digit(n);
    for i in digit_arr {
        if i>=arr.len() || arr[i] {return false;}
        arr[i] = true;
    }
    return true;
}

#[cfg(test)]
fn check_pan(arr:&Vec<bool>) -> bool {
    for b in arr {
        if *b == false {return false;}
    }
    return true;
}

#[cfg(test)]
fn to_digit(mut n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    while n > 0 {
        v.push(n % 10);  n /= 10;
    }
    return v;
}

#[cfg(test)]
fn concat_num(pan:&Vec<usize>) -> String{
    let mut s:String = String::new();
    for i in pan {       
        s.push_str((*i).to_string().as_str());       
    }
    return s;
}

 

 

풀이 2 

---

HackerRank에서는, pandigital을 출력하는 것이 아니고, $x$ 값들을 출력해야 한다. 

즉,  2에서 n까지의 수 중에서 "9 pandigital"이 되는 수 혹은 "8 pandigital"이 되는 수들을 오름차순으로 구하는 것.

여기서 k=9이면 "9 pandigital"을, k=8이면  "8 pandigital"을 구하는 것. "8 pandigital"이라는 것은 1~8까지의 8자리 수가 모두 있는 것 

 

 

Euler Project에서는 가장 큰 pandigital을 구하는 것이었기에, 가장 큰 수 일 수 있는 4자리 수 9876에서부터 수를 작게 하면서 pandigital이 되는 첫 번째 수를 찾아내면 됐었다.

 

그러나, HackerRank의 문제는 2~n까지의 수에 대해서, 모든 $x$를 구하는 것이기에, $x=2$에서부터 시작해서 n까지 증가시키면서, pandigital을 만족되면, 그때의 $x$값을 벡터에 저장해 뒀다가, 나중에 이 벡터 안의 모든 값을 출력하면 되겠다.

 

#[test]
fn test1(){
    print_ans(solve1(100,8));
    // print_ans(solve1(100000,9));
}

#[cfg(test)]
fn print_ans(v:Vec<usize>){
    for i in v {println!("{i}");}
}

#[cfg(test)]
fn solve1(n:usize, k:usize) -> Vec<usize> {
    let mut ans:Vec<usize> = Vec::new();
    for i in 2..=n {
        let mut t:Vec<bool> = vec![false;10]; 
        t[0] = true; t[9] = true;
        let mut pan:Vec<usize> = Vec::new();
        for j in 1..=k {
            let p = i*j; pan.push(p);
            if insert_digit(p, &mut t) == false {break;}
            if check_pan(&t) {
                ans.push(i); break;
            }
        }
    }
    return ans;
}

• 만족하는 $x$ 값들을 저장하는 벡터로 ans를 정의했다.
• check_pan(&t)일 때, 함수를 종료하지 않고, 그때의 $x$ 값인 $i$를 보관했다.

 

HackerRank에 업로드된 코드는 아래와 같다.

use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut stdin_iterator = stdin.lock().lines();

    let first_multiple_input: Vec<String> = stdin_iterator.next().unwrap().unwrap()
            .split(' ')
            .map(|s| s.to_string())
            .collect();

    let n = first_multiple_input[0].trim().parse::<usize>().unwrap();
    let k = first_multiple_input[1].trim().parse::<usize>().unwrap();
    
    print_ans(solve1(n,k));    
}

fn print_ans(v:Vec<usize>){
    for i in v {println!("{i}");}
}

fn solve1(n:usize, k:usize) -> Vec<usize> {
    let mut ans:Vec<usize> = Vec::new();
    for i in 2..=n {
        let mut t:Vec<bool> = vec![false;k+1]; t[0] = true;
        let mut pan:Vec<usize> = Vec::new();
        for j in 1..=k {
            let p = i*j; pan.push(p);
            if insert_digit(p, &mut t) == false {break;}
            if check_pan(&t) {
                ans.push(i); break;
            }
        }
    }
    return ans;
}

fn insert_digit(n:usize, arr:&mut Vec<bool>) -> bool {
    let digit_arr:Vec<usize> = to_digit(n);
    for i in digit_arr {
        if i>=arr.len() || arr[i] {return false;}
        arr[i] = true;
    }
    return true;
}

fn check_pan(arr:&Vec<bool>) -> bool {
    for b in arr {
        if *b == false {return false;}
    }
    return true;
}

fn to_digit(mut n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    while n > 0 {
        v.push(n % 10);  n /= 10;
    }
    return v;
}

 

총평

---

그냥 문제의 조건대로 프로그래밍을 하면 된다. 평이한 문제.

 

전체 소스코드

---

p38.rs 

#[test]
fn test(){
    assert_eq!("932718654".to_string(), solve());
}

#[cfg(test)]
fn solve() -> String{
    for i in (5123..=9876).rev(){   
        let mut t:Vec<bool> = vec![false;10]; t[0] = true;
        let mut pan:Vec<usize> = Vec::new();
        for j in 1..=9 {
            let p = i*j; pan.push(p);
            if insert_digit(p, &mut t) == false {break;}
            if check_pan(&t) {return concat_num(&pan);}
        }
    }
    return "0".to_string();
}

#[cfg(test)]
fn insert_digit(n:usize, arr:&mut Vec<bool>) -> bool {
    let digit_arr:Vec<usize> = to_digit(n);
    for i in digit_arr {
        if i>=arr.len() || arr[i] {return false;}
        arr[i] = true;
    }
    return true;
}

#[cfg(test)]
fn check_pan(arr:&Vec<bool>) -> bool {
    for b in arr {
        if *b == false {return false;}
    }
    return true;
}

#[cfg(test)]
fn to_digit(mut n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = Vec::new();
    while n > 0 {
        v.push(n % 10);  n /= 10;
    }
    return v;
}

#[cfg(test)]
fn concat_num(pan:&Vec<usize>) -> String{
    let mut s:String = String::new();
    for i in pan {       
        s.push_str((*i).to_string().as_str());       
    }
    return s;
}

//-------------------------
// HackerRank:
#[test]
fn test1(){
    print_ans(solve1(100,8));
    // print_ans(solve1(100000,9));
}

#[cfg(test)]
fn print_ans(v:Vec<usize>){
    for i in v {println!("{i}");}
}

#[cfg(test)]
fn solve1(n:usize, k:usize) -> Vec<usize> {
    let mut ans:Vec<usize> = Vec::new();
    for i in 2..=n {
        let mut t:Vec<bool> = vec![false;10]; t[0] = true; 
        let mut pan:Vec<usize> = Vec::new();
        for j in 1..=k {
            let p = i*j; pan.push(p);
            if insert_digit(p, &mut t) == false {break;}
            if check_pan(&t) {
                ans.push(i); break;
            }
        }
    }
    return ans;
}

 

끝