[Node.js & Rust] 백준 24460 - 특별상이라도 받고 싶어

문제

아. 재귀의 세상. 또 와버렸다.

접근

문제의 규칙이 중요하다.

이 문제의 규칙은 곧 이 문제를 풀기 위한 알고리즘 그 자체라는 사실!

종료 조건 : 영역의 크기가 1 * 1 이라면, 그 칸의 추첨 번호로 당첨
재귀 조건 : N * N 이면 같은 크기의 정사각형 네 개로 나눈다
결합 : 네 구역에서 재귀적으로 뽑힌 네 명의 추첨 번호 중 두 번쨰로 작은 값을 최정 결과로 선택한다.

아.

써있는 그대로 구현하면 되겠다!

라는 방식으로 접근했다.

따라서 구현부는 다음과 같이 나누어진다.

입력과 배열(점수)를 저장하기
해당 과정을 재귀적으로 처리할 함수를 구현하기

이제 이 문제는 끝난거나 다름 없다.

야호!

라기에는 생각보다 어렵단말이지.

그래서 Node 와 Rust로 두개 해봤다.

구현

1. 기본 케이스 “종료”

가장 작은 1x1에 도달 -> 배열에서 해당 위치의 값을 반환, 재귀 종료

2. 재귀 호출

현재 크기를 절반으로 나눈 후, 네 구역에 대해 재귀호출을 진행한다.

왼쪽 위 : (r,c)
오른쪽 위 : (r , c + half)
왼쪽 아래 : (r + half, c)
오른쪽 아래: (r + half, c + half)

3. 결합

네 개의 결과를 모두 배열에 모은 후, 정렬한다.
두 번째 요소 (idx = 1)를 반환한다.

이러면 정답이 나온다.

각자 값을 가지고 와서 합쳐진 다음, 결과 반환이라고 보면 됨.

정답 코드 (Node)

const fs = require("fs");

const input = fs
  .readFileSync("dev/stdin")
  .toString()
  .replace(/\r/g, "")
  .trim()
  .split("\n");

const N = parseInt(input[0]);

const arr = new Array(N);

for (let i = 1; i <= N; i++) {
  const line = input[i];

  const numLine = line.split(" ").map(Number);

  arr[i - 1] = numLine;
}
const ans = rec_sol(N, 0, 0);

console.log(ans);

/**
 *
 * @param {number} size
 * @param {number} r
 * @param {number} c
 * @returns
 */
function rec_sol(size, r, c) {
  if (size === 1) {
    return arr[r][c];
  }

  const half = size / 2;

  const res = [
    rec_sol(half, r, c),
    rec_sol(half, r, c + half),
    rec_sol(half, r + half, c),
    rec_sol(half, r + half, c + half),
  ];
  res.sort((a, b) => a - b);

  return res[1];
}

정답 코드 (Rust)

//! ### 백준 24460 - 특별상이라도 받고싶어
//!
//! 실버 3
//!
//! 첫 줄 정수 N
//!
//! 두번째부터 N개 줄의 i번째 줄에 i번에 줄에 있는 의자의 추첨번호
//!
//! N개의 추첨번호가 공백으로 주어진다.
//!
use std::io::{self, Read};

pub fn main() {
    let mut input = String::new();
    io::stdin()
        .read_to_string(&mut input)
        .expect("데이터가 없는데요");
    let mut tokens = input.split_ascii_whitespace();

    let n: usize = tokens.next().unwrap().parse().expect("N Parse error");

    let mut arr: Vec<Vec<i32>> = Vec::with_capacity(n);

    // arr에 추첨번호 입력
    for _i in 0..n {
        let mut row: Vec<i32> = Vec::with_capacity(n);
        for _j in 0..n {
            let val: i32 = tokens.next().unwrap().parse().unwrap();
            row.push(val);
        }
        arr.push(row);
    }

    // 분할 정복 함수 호출
    let res = solve(&arr, n, 0, 0);

    // 출력
    println!("{}", res);
}

fn solve(arr: &Vec<Vec<i32>>, size: usize, r: usize, c: usize) -> i32 {
    if size == 1 {
        return arr[r][c];
    }

    let half = size / 2;

    let mut res: Vec<i32> = vec![
        solve(arr, half, r, c),
        solve(arr, half, r + half, c),
        solve(arr, half, r, c + half),
        solve(arr, half, r + half, c + half),
    ];

    res.sort_unstable();
    return res[1];
}

후기

역시 재귀가 생각보다 재밌다.

여전히 어떻게 잘 돌아가는 건지는 조금 직관적으로 이해가 되지는 않지만

챠르르르륵 재귀를 마친 함수들이 결과를 만드는 과정을 보면, 꽤나 감동적이지 않은가.

수학공부는 역시 필수야.

그리고 읽기 좋은 주석을 남기는 연습과, 의미 있는 변수명을 만들기 위해 노력하자.

아자아자. 화이팅.

[Node.js] [Rust] 백준 24460 - 특별상이라도 받고 싶어

분할정복이 왜 빠른건지 여전히 모르겠음.