반응형
문제 (English)
The four adjacent digits in the 1000-digit number that have the greatest product are 9 X 9 X 8 X 9 = 5832.
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product.
Answer: 23514624000
문제 분석
1000개의 연속된 숫자가 있을 때, k개의 연속된 자리의 수를 곱한 것에 대한 최댓값을 구하는 문제이다.
문자열로 된 1000개의 숫자를 숫자배열로 읽어낸 후, k개의 연속된 자리에 대한 곱을 해가면서 최댓값을 구하면 되겠다.
풀이 1
풀이 방법은 간단하다.
1) 숫자로 된 문자열 num을 읽는다.
2) 문자열을 숫자 배열로 변환한다.
3) 배열의 처음부터 k 개씩 잘라내고, k개의 숫자를 곱하면서 최댓값을 구한다.
문제는 어떻게 문자열을 숫자 배열로 바꾸고, 숫자 배열에서 k개를 잘라내느냐의 프로그래밍 기술 문제.
Rust에 있는 Iterator Adapter를 이용하면 간단히 계산된다.
fn answer(_n:usize, k:usize, num: String) -> u64{
num
.chars() //1. string을 char 배열로 변환
.filter_map(|c| c.to_digit(10)) //2. 십진수 숫자로 변환
.map(|n| n as u64) //3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
.collect::<Vec<_>>() //4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
.windows(k) //5. k 만큼씩 값을 추출
.map(|win| win.iter().product()) //6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
.max() //7. 곱연산한 각 iter중에서 가장 큰 값 추출
.unwrap() //8. max에 의해 나온 Option에서 Some값만 추출
}
문자열의 크기 n은 불필요한 정보
num 문자열에 있는 각 문자 c를 c.to_digit(10)을 이용해서 숫자로 바꾸고, windows(k)를 통해 k개로 짤라매면서 곱셈을 하고, 최댓값을 구한다.
이번 풀이에서는 테스트 케이스에 큰 문자열이 있기에, 테스트 케이스를 별도 텍스트파일로 만들고, 이 텍스트 파일을 읽으면서 테스트가 진행되도록 했다.
#[test]
fn test(){
let ans:[u64; 4] = [3150, 0, 5832, 23514624000];
// let ans:[u64; 2] = [3150, 0,];
let mut lines = std::fs::read_to_string("test_input/p8_input.txt").unwrap().lines().map(String::from).collect::<Vec<String>>().into_iter();
let t = lines.next().unwrap().trim().parse::<i32>().unwrap();
for i in 0..t{
let nk:Vec<String> = lines.next().unwrap().split(' ').map(|s| s.to_string()).collect();
let n = nk[0].trim().parse::<i32>().unwrap();
let k = nk[1].trim().parse::<i32>().unwrap();
let num = lines.next().unwrap();
assert_eq!(ans[i as usize], answer(n as usize,k as usize,num));
}
}
#[cfg(test)]
fn answer(_n:usize, k:usize, num: String) -> u64{
num
.chars() //1. string을 char 배열로 변환
.filter_map(|c| c.to_digit(10)) //2. 십진수 숫자로 변환
.map(|n| n as u64) //3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
.collect::<Vec<_>>() //4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
.windows(k) //5. k 만큼씩 값을 추출
.map(|win| win.iter().product()) //6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
.max() //7. 곱연산한 각 iter중에서 가장 큰 값 추출
.unwrap() //8. max에 의해 나온 Option에서 Some값만 추출
}
테스트 파일은, src 폴더가 있는 cargo 실행 루트를 기준으로 test_input/p8_input.txt 파일이다.
4
10 5
3675356291
10 5
2709360626
1000 4
7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
1000 13
7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
테스트 input은, 처음에 문제의 개수 t가 오고(여기서는 4),
그 다음 줄에 n, k가 오고,
그다음 줄에 문자열인 num이 오는 구조
여기서는 문자열에 개행문자가 없이 다 이어진 것으로 가정하고 처리했는데, Project Euler 사이트의 문제에는 1000개의 문자에 대해 한 줄에 50개씩 20개의 Row로 되어 있다.
이 경우는 아래와 같이 문자열을 읽어내면 된다.
const INPUT: &str = r"
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450";
//RUST의 Iterator Adapter들을 이용해서 구해봄
fn answer(w_size: usize) -> u64{
INPUT
.chars() //1. string을 char 배열로 변환
.filter_map(|c| c.to_digit(10)) //2. 십진수 숫자로 변환
.map(|n| n as u64) //3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
.collect::<Vec<_>>() //4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
.windows(w_size) //5. w_size 만큼씩 값을 추출
.map(|win| win.iter().product()) //6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
.max() //7. 곱연산한 각 iter중에서 가장 큰 값 추출
.unwrap() //8. max에 의해 나온 Option에서 Some값만 추출
}
풀이 2
풀이 1에서는 Rust의 Iterator Adapter를 이용해서 간단히 풀었는데, 일반적인 for 루프를 써가며 한번 풀어본다.
/-----------------------------------
// - Iterator Adapter가 아닌, 그냥 일반적인 방법으로 차근차근 풀어본 방법
// - Iterator보다 더 빠르다.
#[test]
fn test1(){
let ans:[u64; 4] = [3150, 0, 5832, 23514624000];
// let ans:[u64; 2] = [3150, 0,];
let mut lines = std::fs::read_to_string("test_input/p8_input.txt").unwrap().lines().map(String::from).collect::<Vec<String>>().into_iter();
let t = lines.next().unwrap().trim().parse::<i32>().unwrap();
for i in 0..t{
let nk:Vec<String> = lines.next().unwrap().split(' ').map(|s| s.to_string()).collect();
let n = nk[0].trim().parse::<i32>().unwrap();
let k = nk[1].trim().parse::<i32>().unwrap();
let num = lines.next().unwrap();
assert_eq!(ans[i as usize], answer1(n as usize,k as usize,num));
}
}
#[cfg(test)]
fn answer1(_n:usize, k:usize, num:String) -> u64{
//1. string을 char 배열로 변환
let c_arr = num.chars();
//2. 십진수 숫자로 변환
//3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
//4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
let mut v: Vec<u64> = Vec::new();
for c in c_arr{
match c.to_digit(10) {
Some(num) => v.push(num as u64),
None => {},
}
}
//5. k 만큼씩 값을 추출
//6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
//7. 곱연산한 각 iter중에서 가장 큰 값 추출
let mut max: u64 = 0;
let v_size = v.len();
'outer: for i in 0..v_size{
let mut p: u64 = 1;
for j in i..(i+k){
if j >= v_size {
break 'outer ;
}
p *= v[j];
}
if p > max {
max = p;
}
}
return max;
}
풀이 3
풀이 1은 너무 Iterator Adapter를 썼고, 풀이 2는 너무 old 스타일로 코딩이 되었다.
일부 명확하게 Iterator Adapter를 써도 괜찮은 것은 사용해서 코드를 작성해 본다.
코드 중에, k개의 숫자 중에 0이 발견되면, 그 숫자들에 대한 곱은 0이기에, 더 이상 곱하지 않고 p=0으로 처리한 부분 주의.
//--------------------------------------
//- 일부는 Iterator Adapter를 사용
//- 숫자중에 0이 있으면 더 이상 곱셈연산하지 않도록 해서, 연산횟수 줄인버전
#[test]
fn test2(){
let ans:[u64; 4] = [3150, 0, 5832, 23514624000];
// let ans:[u64; 2] = [3150, 0,];
let mut lines = std::fs::read_to_string("test_input/p8_input.txt").unwrap().lines().map(String::from).collect::<Vec<String>>().into_iter();
let t = lines.next().unwrap().trim().parse::<i32>().unwrap();
for i in 0..t{
let nk:Vec<String> = lines.next().unwrap().split(' ').map(|s| s.to_string()).collect();
let n = nk[0].trim().parse::<i32>().unwrap();
let k = nk[1].trim().parse::<i32>().unwrap();
let num = lines.next().unwrap();
assert_eq!(ans[i as usize], answer2(n as usize,k as usize,num));
}
}
#[cfg(test)]
fn answer2(_n:usize, k:usize, num:String) -> u64{
//1. string을 char 배열로 변환
let c_arr = num.chars();
//2. 십진수 숫자로 변환
//3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
//4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
let mut v: Vec<u64> = Vec::new();
for c in c_arr{
match c.to_digit(10) {
Some(num) => v.push(num as u64),
None => {},
}
}
//5. w_size 만큼씩 값을 추출
//6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
//7. 곱연산한 각 iter중에서 가장 큰 값 추출
let mut max: u64 = 0;
let v_size = v.len();
'outer: for i in 0..v_size{
let mut p: u64 = 1;
for j in i..(i+k){
if j >= v_size { break 'outer; }
if v[j] == 0 {p=0; break; } //0이면 더 이상 곱을할 필요 없다.
p *= v[j];
}
if p > max {
max = p;
}
}
return max;
}총평
알고리즘은 간단하다. 다만, Rust에서 어떻게 문자열을 읽고, 이것을 어떻게 k개로 자르고, 각 수를 어떻게 곱하는지에 대한 코딩 스킬이 필요한 문제.
전체 소스코드
p8.rs
#[test]
fn test(){
let ans:[u64; 4] = [3150, 0, 5832, 23514624000];
// let ans:[u64; 2] = [3150, 0,];
let mut lines = std::fs::read_to_string("test_input/p8_input.txt").unwrap().lines().map(String::from).collect::<Vec<String>>().into_iter();
let t = lines.next().unwrap().trim().parse::<i32>().unwrap();
for i in 0..t{
let nk:Vec<String> = lines.next().unwrap().split(' ').map(|s| s.to_string()).collect();
let n = nk[0].trim().parse::<i32>().unwrap();
let k = nk[1].trim().parse::<i32>().unwrap();
let num = lines.next().unwrap();
assert_eq!(ans[i as usize], answer(n as usize,k as usize,num));
}
}
#[cfg(test)]
fn answer(_n:usize, k:usize, num: String) -> u64{
num
.chars() //1. string을 char 배열로 변환
.filter_map(|c| c.to_digit(10)) //2. 십진수 숫자로 변환
.map(|n| n as u64) //3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
.collect::<Vec<_>>() //4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
.windows(k) //5. k 만큼씩 값을 추출
.map(|win| win.iter().product()) //6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
.max() //7. 곱연산한 각 iter중에서 가장 큰 값 추출
.unwrap() //8. max에 의해 나온 Option에서 Some값만 추출
}
//-----------------------------------
// - Iterator Adapter가 아닌, 그냥 일반적인 방법으로 차근차근 풀어본 방법
// - Iterator보다 더 빠르다.
#[test]
fn test1(){
let ans:[u64; 4] = [3150, 0, 5832, 23514624000];
// let ans:[u64; 2] = [3150, 0,];
let mut lines = std::fs::read_to_string("test_input/p8_input.txt").unwrap().lines().map(String::from).collect::<Vec<String>>().into_iter();
let t = lines.next().unwrap().trim().parse::<i32>().unwrap();
for i in 0..t{
let nk:Vec<String> = lines.next().unwrap().split(' ').map(|s| s.to_string()).collect();
let n = nk[0].trim().parse::<i32>().unwrap();
let k = nk[1].trim().parse::<i32>().unwrap();
let num = lines.next().unwrap();
assert_eq!(ans[i as usize], answer1(n as usize,k as usize,num));
}
}
#[cfg(test)]
fn answer1(_n:usize, k:usize, num:String) -> u64{
//1. string을 char 배열로 변환
let c_arr = num.chars();
//2. 십진수 숫자로 변환
//3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
//4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
let mut v: Vec<u64> = Vec::new();
for c in c_arr{
match c.to_digit(10) {
Some(num) => v.push(num as u64),
None => {},
}
}
//5. k 만큼씩 값을 추출
//6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
//7. 곱연산한 각 iter중에서 가장 큰 값 추출
let mut max: u64 = 0;
let v_size = v.len();
'outer: for i in 0..v_size{
let mut p: u64 = 1;
for j in i..(i+k){
if j >= v_size {
break 'outer ;
}
p *= v[j];
}
if p > max {
max = p;
}
}
return max;
}
//--------------------------------------
//- 일부는 Iterator Adapter를 사용
//- 숫자중에 0이 있으면 더 이상 곱셈연산하지 않도록 해서, 연산횟수 줄인버전
#[test]
fn test2(){
let ans:[u64; 4] = [3150, 0, 5832, 23514624000];
// let ans:[u64; 2] = [3150, 0,];
let mut lines = std::fs::read_to_string("test_input/p8_input.txt").unwrap().lines().map(String::from).collect::<Vec<String>>().into_iter();
let t = lines.next().unwrap().trim().parse::<i32>().unwrap();
for i in 0..t{
let nk:Vec<String> = lines.next().unwrap().split(' ').map(|s| s.to_string()).collect();
let n = nk[0].trim().parse::<i32>().unwrap();
let k = nk[1].trim().parse::<i32>().unwrap();
let num = lines.next().unwrap();
assert_eq!(ans[i as usize], answer2(n as usize,k as usize,num));
}
}
#[cfg(test)]
fn answer2(_n:usize, k:usize, num:String) -> u64{
//1. string을 char 배열로 변환
let c_arr = num.chars();
//2. 십진수 숫자로 변환
//3. u64로 변환. b/c 최종결괏값이 u64형태 리턴
//4. Vector로 변환: u64형태의 숫자 1000개짜리 벡터
let mut v: Vec<u64> = Vec::new();
for c in c_arr{
match c.to_digit(10) {
Some(num) => v.push(num as u64),
None => {},
}
}
//5. w_size 만큼씩 값을 추출
//6. w_size 개수 만큼의 값들에 대해서 각각 곱연산 수행
//7. 곱연산한 각 iter중에서 가장 큰 값 추출
let mut max: u64 = 0;
let v_size = v.len();
'outer: for i in 0..v_size{
let mut p: u64 = 1;
for j in i..(i+k){
if j >= v_size { break 'outer; }
if v[j] == 0 {p=0; break; } //0이면 더 이상 곱을할 필요 없다.
p *= v[j];
}
if p > max {
max = p;
}
}
return max;
}
끝
반응형
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
| 010. Summation of Primes (k보다 작은 모든 소수의 합 구하기) (0) | 2024.08.14 |
|---|---|
| 009. Special Pythagorean Triplet (합이 k가 되는 피타코라스 수 구하기) (0) | 2024.08.13 |
| 007. 10001st Prime (k번째 소수 구하기) (0) | 2024.08.13 |
| 006. Sum Square Difference ("제곱의 합"과 "합의 제곱"과의 차 구하기) (0) | 2024.08.13 |
| 005. Smallest Multiple (여러 수에 대한 최소공배수 구하기) (0) | 2024.08.13 |