011. Largest Product in a Grid (2차원 격자에서 가로/세로/대각선으로 수 읽고 최대곱 구하기)

​문제 (English)

In the 20 X 20 grid below, four numbers along a diagonal line have been marked in red.

 

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

 

The product of these numbers is 26 X 63 X 78 X 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right or diagonally) in the 20 X 20 grid?

 

Answer: 70600674

문제 분석

---

2차원 배열인 grid형태 데이터에서, 가로로 4칸씩, 세로로 4칸씩, 대각선으로 4칸씩 읽었을 때 만들어지는 수 중에서, 각 수를 곱한 값이 가장 큰 것을 찾으라는 문제.

 

grid에서 가로/세로/대각선으로 움직일 때, 어떻게 index를 바꾸면 되는지만 알면 풀 수 있는 문제.

 

그리고, 2차원 배열 형태의 문자열이 주어질 때, 이것을 읽어서 어떻게 숫자 형태의 2차원 배열/벡터를 만드는지에 대한 연습을 할 수 있는 문제이다.

 

풀이 1 

---

20X20 형태의 문자열이 주어질 때, 이를 20X20의 2중 벡터로 만드는 방법은 다음과 같다.

fn read_grid_data(data:&str) -> Vec<Vec<i32>> {
    let lines = data.trim().lines();
    let mut grid: Vec<Vec<i32>> = Vec::new();
    for line in lines{
        grid.push(line.split_whitespace().filter_map(|s| s.parse().ok()).collect());
    }
    return grid;
}

 

이렇게 읽어낸 grid는 x와 y를 이용해서 grid[x][y]로 읽어 낼 수 있다. 

1) 가로로 움직인다는 것은, x의 값을 변경시키는 것이고, x를 증가시키면 오른편 가로로 움직이는 것

2) 세로로 움직인다는 것은, y를 변경시키는 것. y가 증가되면 밑 방향으로 움직이는 것

3) 대각선은 x,y가 모두 변경되는 것이다. 우측 아랫 방향이면 x와 y를 모두 증가시키면 됨.

    외쪽 아랫방향이면 x는 감소, y는 증가

 

위와 같은 이동방법을 이용해서 코딩을 하면 다음과 같다.

fn answer(grid:&Vec<Vec<i32>>) -> i32{
    //1. horizontal
    let mut max: i32 = 1;
    for h in grid {  //to prevent to be moved
        for i in 0..h.len()-3{
            let p = h[i] * h[i+1] * h[i+2] * h[i+3];
            if p > max { max = p; }
        }
    }

    //2. vertical
    for c in 0..grid[0].len() {
        for r in 0..grid.len()-3{
            let p = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c];
            if p > max { max = p; }
        }
    }
    
    //3. diagonal_rightdown
    for r in 0..grid.len()-3{
        for c in 0..grid[r].len()-3{
            let p = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3];
            if p > max { max = p; }
        }
    }

    //4. diagonal_leftdown
    for r in 0..grid.len()-3{
        for c in 3..grid[r].len(){
            let p = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3];
            if p > max { max = p; }
        }
    }

    return max;
}

풀이 2 

---

풀이1로도 hackerrank 사이트 풀이를 통과할 수 있으나, 좀 더 속도 향상을 할 수 있다.

 

풀이1에서는 가로/세로/대각선에 대해 각각 for 루프를 돌렸는데, 하나의 for 루프에서 가로/세로/대각선 이동을 처리할 수도 있겠다. 이러면 좀 더 속도 향상이 된다.

fn answer1(grid:&Vec<Vec<i32>>) -> i32{
    let mut max: i32 = 1;
    for r in 0..grid.len(){    
        for c in 0..grid[r].len(){
            //1. horizontal
            if c < grid[r].len() -3 {
                let p = grid[r][c] * grid[r][c+1] * grid[r][c+2] * grid[r][c+3];
                if p > max { max = p; }
            }

            //2. vertical
            if r < grid.len() - 3 {
                let p = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c];
                if p > max { max = p; }
            }

            //3. diagonal_rightdown
            if r < grid.len() - 3 && c < grid[0].len() - 3 {
                let p = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3];
                if p > max { max = p; }
            }

            //4. diagonal_leftdown
            if r < grid.len() - 3 && c > 3{
                let p = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3];
                if p > max { max = p; }
            }
        }
   }
   return max;
}

 

grid 데이터를 읽어내는 것도, 풀이1에서는 lines를 뽑아낸 후 여기서 grid 벡터를 만들어 냈는데, 풀이2에서는 Iterator Adapter 방식만을 써서 grid 벡터를 만들어봤다. (이렇게 했다고 속도가 향상되지는 않는다.)

 

fn read_grid_data1(data:&str) -> Vec<Vec<i32>> {
    let grid: Vec<Vec<i32>> = data.trim().lines()
            .map(|line|{
                line.split_whitespace()
                    .filter_map(|s| s.parse().ok())
                    .collect()
            })
            .collect();
    return grid;
}

 

총평

---

격자 모양의 데이터가 있을 때, 격자의 x,y좌표값을 어떻게 바꾸면 상/하/좌/우로 움직이게 되는지를 연습할 수 있는 문제이다.

 

전체 소스코드

---

p11.rs 

const INPUT: &str = 
    r"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
    49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
    81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
    52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
    22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
    24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
    32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
    67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
    24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
    21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
    78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
    16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
    86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
    19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
    04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
    88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
    04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
    20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
    20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
    01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
    
#[test]
fn test(){
    let grid = read_grid_data(INPUT);
    assert_eq!(70600674, answer(&grid));
}

#[cfg(test)]
fn read_grid_data(data:&str) -> Vec<Vec<i32>> {
    let lines = data.trim().lines();
    let mut grid: Vec<Vec<i32>> = Vec::new();
    for line in lines{
        grid.push(line.split_whitespace().filter_map(|s| s.parse().ok()).collect());
    }
    return grid;
}

#[cfg(test)]
fn answer(grid:&Vec<Vec<i32>>) -> i32{
    //1. horizontal
    let mut max: i32 = 1;
    for h in grid {  //to prevent to be moved
        for i in 0..h.len()-3{
            let p = h[i] * h[i+1] * h[i+2] * h[i+3];
            if p > max { max = p; }
        }
    }

    //2. vertical
    for c in 0..grid[0].len() {
        for r in 0..grid.len()-3{
            let p = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c];
            if p > max { max = p; }
        }
    }
    
    //3. diagonal_rightdown
    for r in 0..grid.len()-3{
        for c in 0..grid[r].len()-3{
            let p = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3];
            if p > max { max = p; }
        }
    }

    //4. diagonal_leftdown
    for r in 0..grid.len()-3{
        for c in 3..grid[r].len(){
            let p = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3];
            if p > max { max = p; }
        }
    }

    return max;
}

//----------------------------------
//하나의 for 루프에서 처리하도록
   
#[test]
fn test1(){
    let grid = read_grid_data1(INPUT);
    assert_eq!(70600674, answer1(&grid));
}

#[cfg(test)]
fn read_grid_data1(data:&str) -> Vec<Vec<i32>> {
    let grid: Vec<Vec<i32>> = data.trim().lines()
            .map(|line|{
                line.split_whitespace()
                    .filter_map(|s| s.parse().ok())
                    .collect()
            })
            .collect();
    return grid;
}

#[cfg(test)]
fn answer1(grid:&Vec<Vec<i32>>) -> i32{
    let mut max: i32 = 1;
    for r in 0..grid.len(){    
        for c in 0..grid[r].len(){
            //1. horizontal
            if c < grid[r].len() -3 {
                let p = grid[r][c] * grid[r][c+1] * grid[r][c+2] * grid[r][c+3];
                if p > max { max = p; }
            }

            //2. vertical
            if r < grid.len() - 3 {
                let p = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c];
                if p > max { max = p; }
            }

            //3. diagonal_rightdown
            if r < grid.len() - 3 && c < grid[0].len() - 3 {
                let p = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3];
                if p > max { max = p; }
            }

            //4. diagonal_leftdown
            if r < grid.len() - 3 && c > 3{
                let p = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3];
                if p > max { max = p; }
            }
        }
   }
   return max;
}

 

끝