017. Number Letter Counts (숫자를 영어로 읽었을 때, 몇 개의 문자가 되는지 구하기)

​문제 (English)

If the numbers 1 to 5 are written out in words: one, two, three, four, five, th20 en there are 3+3+5+4+4=19 letters used in total.

If all the numbers from 1 to 100 (one thousand) inclusive were written out in words, how many letters would be used?

 

NOTE: Do not count spaces or hyphens. For example, 342(three hundred and forty-two) contains 23 letters and 115(one hundred and fifteen) contains letters. The use of "and" when writing out numbers is in compliance with British usage.

 

Answer: 21124

문제 분석

---

십진수로 된 수가 주어졌을 때 어떻게 영어로 읽게 할지, 그 규칙에 따라 코드를 짜게 하는 문제이다.

문제에서 주어진 문자열의 합은, 주어진 수를 영어로 표현할 수 있다면, 그 문자열을 세서 합치면 되는 것.

 

HashMap을 사용해서, 기본되는 수에 대해 영어 문자를 저장해 두고 사용하면 되겠다.

 

Euler Project에서는 이처럼 1에서 1000까지의 수에 대해 영어로 나타냈을 때, 모든 문자열의 합을 구하라고 되어있고, hackerrank에서는 어떤 수 N에 대해 영어로 읽으라고 되어 있다.

 

풀이 1 

---

Euler Project에 있는, 카운트를 세는 문제에 대해서 풀어보자.

 

영어에서 수를 읽는 규칙성을 보면,

• 1~19까지는 딱히 규칙성이 없다. 따라서, Hashmap에 해당 수에 대한 읽기 문자열을 저장해 뒀다가 사용한다.
• 20~99: 십의 자리에 대해서 {twenty, thirty, ...} 처럼 정해져 있고, 그 뒤 1의 자리는 {one, two,..., nine}을 붙이면 된다.
• 100~999: 백의자리를 {one, two..., nine}으로 읽고 그다음에 "hundred and"를 붙이고, 그다음은 1~99까지의 규칙처럼 읽으면 된다. ex) 342: three hundread and forty two
• 1000: one thousand

이런 규칙에 의해 결정되는 문자열 개수를 구하고 더하면 된다.

#[test]
fn test(){
    assert_eq!(19, answer(5)); //2^15=32768, 3+2+7+6+8=26
    assert_eq!(864, answer(100));
    assert_eq!(21124, answer(1000));  
}

#[cfg(test)]
use std::collections::HashMap;
 
// 구분
// 1~19, 20~99, 100~999, 1000
#[cfg(test)]
fn answer(n:u32) -> u32{
    let word_map:HashMap<u32, &str> = HashMap::from(
        [
            (1, "one"),(2, "two"), (3, "three"),(4, "four"),(5, "five"),
            (6, "six"),(7, "seven"),(8, "eight"),(9, "nine"),(10, "ten"),
            (11, "eleven"),(12, "twelve"),(13, "thirteen"),(14, "fourteen"),(15, "fifteen"),
            (16, "sixteen"),(17, "seventeen"),(18, "eighteen"),(19, "nineteen"),
            (20, "twenty"),(30, "thirty"),(40, "forty"),(50, "fifty"),(60, "sixty"),
            (70, "seventy"),(80, "eighty"),(90, "ninety"),
        ]
    );

    let mut sum:u32 = 0;
    for i in 1..=n {
        sum += get_len(i, &word_map);
    }
    return sum;
}

#[cfg(test)]
fn get_len(n:u32, map:&HashMap<u32, &str>) -> u32{
    let len:u32 = match n {
        1..=19 => map[&n].len() as u32,
        20..=99 => from20to99(n, &map),
        100..=999 => from100to999(n, &map),
        1000 => "one thousand".len() as u32 - 1,  //not count the space
        _ => 0,
    };
    return len;
}

//20..=99
//20: twenty, 21: twenty-one
#[cfg(test)]
fn from20to99(n:u32, map:&HashMap<u32, &str>) -> u32{
    let (q,r):(u32,u32) = (n/10, n%10);
    let mut len:u32 = map[&(q*10u32)].len() as u32;
    if r!=0 { //20,30,...,90
        len += map[&r].len() as u32; // "twenty".len() + "two".len(). no hypen counted
    }
    return len;
}

//100..=999
//100: one hundread, 101: one hundread and one, 123: one hundread and twenty-three
#[cfg(test)]
fn from100to999(n:u32, map:&HashMap<u32, &str>) -> u32{
    let (q,r):(u32,u32) = (n/100, n%100);
    let mut len:u32 = map[&q].len() as u32 + "hundred".len() as u32;
    if r!=0 { //101, 112, 224, etc
        if r <= 20 {
            len += "and".len() as u32 + map[&r].len() as u32;
        }else{ //21 ~ 99
            len += "and".len() as u32 + from20to99(r, &map);
        }
    }
    return len;
}

풀이 2 

---

Hackerrank 사이트에 나와 있는 문제를 풀어보자.

 

여기서는 수를 읽을 때의 문자열 개수를 구하는 것이 아닌, 어떤 수를 주고 이 수를 적은 문자열을 출력하는 것이다.

여기서 수는 1에서 $10^{12}$까지의 수로, 꽤 큰 수이다.

 

수를 읽는 것을 규칙화해 보면,

• 1) 1..=999까지,
  • 1..=19: 규칙성이 없다. Hashmap에 각 수에 대한 읽기 문자열을 지정해 두고 사용한다.
  • 20..=99: 십의자리를 {Twenty, Thirty,..., Ninty}로 읽고, 그다음 일의 자리를 읽는다. ex) 21="Twenty One"
  • 100..=99: 백의자리의 수를 {One, Two,.., Nine} 읽고, 그다음에 "Hundred"를 붙이고, 그 다음 남은 1..=99까지의 수를 위의 1..=19 및 200..=99까지의 규칙을 이용해서 읽는다.
• 2) 1000 이상의 수
  • 3자리씩 끊어서, 위 1..=999까지의 규칙으로 읽고, 첫 번째 3자리 다음에는 "Thousand", 그다음 3자리에 대해서는 "Million", 그다음은 "Billion", 그 다음은 "Trillion"을 붙인다. ex) 104382426112 = "One Hundred Four Billion Three Hundred Eighty Two Million Four Hundred Twenty Six Thousand One Hundred Twelve"

#[test]
fn test_hacker(){    
    assert_eq!("One Hundred Four Billion Three Hundred Eighty Two Million Four Hundred Twenty Six Thousand One Hundred Twelve",answer_hacker(104382426112));
}

#[cfg(test)]
fn answer_hacker(mut n:u64) -> String{
    let word_map:HashMap<usize, &str> = HashMap::from(
        [
            (1, "One"),(2, "Two"), (3, "Three"),(4, "Four"),(5, "Five"),
            (6, "Six"),(7, "Seven"),(8, "Eight"),(9, "Nine"),(10, "Ten"),
            (11, "Eleven"),(12, "Twelve"),(13, "Thirteen"),(14, "Fourteen"),(15, "Fifteen"),
            (16, "Sixteen"),(17, "Seventeen"),(18, "Eighteen"),(19, "Nineteen"),
            (20, "Twenty"),(30, "Thirty"),(40, "Forty"),(50, "Fifty"),(60, "Sixty"),
            (70, "Seventy"),(80, "Eighty"),(90, "Ninety"),            
        ]
    );

    let num_str:String = match n {
        1..=999 => s_1to999(n as usize, &word_map),         
        _ => s_over_1000(n as usize, &word_map),        
    };
    return num_str;
}

#[cfg(test)]
fn s_1to999(n:usize, map:&HashMap<usize, &str>) -> String{
    match n {
        1..=99 => s_10(n,map),
        100..=999 => s_100(n,map),
        _ => "".to_string(),
    }
}

#[cfg(test)] 
//1..99
//20: twenty, 21: twenty one
fn s_10(n:usize, map:&HashMap<usize, &str>) -> String{    
    let mut s:String = "".to_string();
    match n {
        1..=20 => s.push_str(map[&n]),
        21..=99 => {let (q,r):(usize,usize) = (n/10, n%10);
                    s.push_str(map[&(q*10)]); 
                    if r != 0 {
                        s.push_str(" "); s.push_str(map[&r]);}
                    },                    
        _ =>(),
        }    
    return s;
}
 
#[cfg(test)]
// 100..=999
fn s_100(n:usize, map:&HashMap<usize, &str>) -> String{
    let mut s:String = "".to_string();

    // x Hundread
    let (q,r):(usize,usize) = (n/100, n%100);        
    s.push_str(map[&q]);  s.push_str(" Hundred");

    // 100, 200,..
    if r != 0 {
       s.push_str(" ");   s.push_str(s_10(r, map).as_str());
    }    
    return s;
}

#[cfg(test)]
// 789456123
fn s_over_1000(mut n:usize, map:&HashMap<usize, &str>) -> String{
    let mut v:Vec<String> = Vec::new();
    let unit_str:Vec<&str> = vec!["Thousand", "Million", "Billion", "Trillion"];
    let mut i:usize = 0;
    while n >= 1 {                
        //1. 100..=999
        let r = n % 1000;
        if r != 0 { v.push(format!("{}",s_1to999(r, map))); }

        //2. >= 1000
        n /= 1000;
        if n % 1000 > 0 { v.push(format!(" {} ",unit_str[i])); }
        i += 1;
    }
    return v.into_iter().rev().collect::<String>();    
}

 

총평

---

풀이 2에서, 수에 대해 읽는 문자열을 만드는 함수에 대해 좀 더 compact 한 코드를 만들 수도 있을 것으로 보이나, 더 손대기 싫어서 그냥 놔둔다.

 

전체 소스코드

---

p17.rs 

#[test]
fn test(){
    assert_eq!(19, answer(5)); //2^15=32768, 3+2+7+6+8=26
    assert_eq!(864, answer(100));
    assert_eq!(21124, answer(1000));  
}

#[cfg(test)]
use std::collections::HashMap;
 
// 구분
// 1~19, 20~99, 100~999, 1000
#[cfg(test)]
fn answer(n:u32) -> u32{
    let word_map:HashMap<u32, &str> = HashMap::from(
        [
            (1, "one"),(2, "two"), (3, "three"),(4, "four"),(5, "five"),
            (6, "six"),(7, "seven"),(8, "eight"),(9, "nine"),(10, "ten"),
            (11, "eleven"),(12, "twelve"),(13, "thirteen"),(14, "fourteen"),(15, "fifteen"),
            (16, "sixteen"),(17, "seventeen"),(18, "eighteen"),(19, "nineteen"),
            (20, "twenty"),(30, "thirty"),(40, "forty"),(50, "fifty"),(60, "sixty"),
            (70, "seventy"),(80, "eighty"),(90, "ninety"),
        ]
    );

    let mut sum:u32 = 0;
    for i in 1..=n {
        sum += get_len(i, &word_map);
    }
    return sum;
}

#[cfg(test)]
fn get_len(n:u32, map:&HashMap<u32, &str>) -> u32{
    let len:u32 = match n {
        1..=19 => map[&n].len() as u32,
        20..=99 => from20to99(n, &map),
        100..=999 => from100to999(n, &map),
        1000 => "one thousand".len() as u32 - 1,  //not count the space
        _ => 0,
    };
    return len;
}

//20..=99
//20: twenty, 21: twenty-one
#[cfg(test)]
fn from20to99(n:u32, map:&HashMap<u32, &str>) -> u32{
    let (q,r):(u32,u32) = (n/10, n%10);
    let mut len:u32 = map[&(q*10u32)].len() as u32;
    if r!=0 { //20,30,...,90
        len += map[&r].len() as u32; // "twenty".len() + "two".len(). no hypen counted
    }
    return len;
}

//100..=999
//100: one hundread, 101: one hundread and one, 123: one hundread and twenty-three
#[cfg(test)]
fn from100to999(n:u32, map:&HashMap<u32, &str>) -> u32{
    let (q,r):(u32,u32) = (n/100, n%100);
    let mut len:u32 = map[&q].len() as u32 + "hundred".len() as u32;
    if r!=0 { //101, 112, 224, etc
        if r <= 20 {
            len += "and".len() as u32 + map[&r].len() as u32;
        }else{ //21 ~ 99
            len += "and".len() as u32 + from20to99(r, &map);
        }
    }
    return len;
}

//------------------------
#[test]
fn test_hacker(){    
    assert_eq!("One Hundred Four Billion Three Hundred Eighty Two Million Four Hundred Twenty Six Thousand One Hundred Twelve",answer_hacker(104382426112));
}

#[cfg(test)]
fn answer_hacker(mut n:u64) -> String{
    let word_map:HashMap<usize, &str> = HashMap::from(
        [
            (1, "One"),(2, "Two"), (3, "Three"),(4, "Four"),(5, "Five"),
            (6, "Six"),(7, "Seven"),(8, "Eight"),(9, "Nine"),(10, "Ten"),
            (11, "Eleven"),(12, "Twelve"),(13, "Thirteen"),(14, "Fourteen"),(15, "Fifteen"),
            (16, "Sixteen"),(17, "Seventeen"),(18, "Eighteen"),(19, "Nineteen"),
            (20, "Twenty"),(30, "Thirty"),(40, "Forty"),(50, "Fifty"),(60, "Sixty"),
            (70, "Seventy"),(80, "Eighty"),(90, "Ninety"),            
        ]
    );

    let num_str:String = match n {
        1..=999 => s_1to999(n as usize, &word_map),         
        _ => s_over_1000(n as usize, &word_map),        
    };
    return num_str;
}

#[cfg(test)]
fn s_1to999(n:usize, map:&HashMap<usize, &str>) -> String{
    match n {
        1..=99 => s_10(n,map),
        100..=999 => s_100(n,map),
        _ => "".to_string(),
    }
}

#[cfg(test)] 
//1..99
//20: twenty, 21: twenty one
fn s_10(n:usize, map:&HashMap<usize, &str>) -> String{    
    let mut s:String = "".to_string();
    match n {
        1..=20 => s.push_str(map[&n]),
        21..=99 => {let (q,r):(usize,usize) = (n/10, n%10);
                    s.push_str(map[&(q*10)]); 
                    if r != 0 {
                        s.push_str(" "); s.push_str(map[&r]);}
                    },                    
        _ =>(),
        }    
    return s;
}
 
#[cfg(test)]
// 100..=999
fn s_100(n:usize, map:&HashMap<usize, &str>) -> String{
    let mut s:String = "".to_string();

    // x Hundread
    let (q,r):(usize,usize) = (n/100, n%100);        
    s.push_str(map[&q]);  s.push_str(" Hundred");

    // 100, 200,..
    if r != 0 {
       s.push_str(" ");   s.push_str(s_10(r, map).as_str());
    }    
    return s;
}

#[cfg(test)]
// 789456123
fn s_over_1000(mut n:usize, map:&HashMap<usize, &str>) -> String{
    let mut v:Vec<String> = Vec::new();
    let unit_str:Vec<&str> = vec!["Thousand", "Million", "Billion", "Trillion"];
    let mut i:usize = 0;
    while n >= 1 {                
        //1. 100..=999
        let r = n % 1000;
        if r != 0 { v.push(format!("{}",s_1to999(r, map))); }

        //2. >= 1000
        n /= 1000;
        if n % 1000 > 0 { v.push(format!(" {} ",unit_str[i])); }
        i += 1;
    }
    return v.into_iter().rev().collect::<String>();    
}

 

끝