[Rust] 교점에 별 만들기

프로그래머스는 Rust 언어를 지원하지 않아, 해당 코드는 정답을 돌려본 것이 아닌 Java로 푼 문제로 Rust로 바꿔 풀어본 코드입니다.

문제 요약

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

제한사항

• line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
  • line의 가로(열) 길이는 3입니다.
  • line의 각 원소는 [A, B, C] 형태입니다.
  • A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
  • 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
  • A = 0이면서 B = 0인 경우는 주어지지 않습니다.
• 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

입출력 예

line	result
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["*.*"]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

참고 사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87377

풀이

풀이법

• 별도의 알고리즘이 있는 것이 아닌, 단순히 주어진 식을 적용해서 교점을 찾아 리스트에 적용해둔 후, 문자열로 변환하는 문제였다.
• 풀이 순서
  1. 입력으로 주어진 입력들의 모든 조합을 탐색
  2. 조합을 탐색하면서 두 직선간의 정수 교점을 찾아 리스트에 저장하며, 격자판의 필요 크기를 조정해 나아감
  3. 격자판에 리스트에 저장된 교점들을 표시
  4. 격자판을 탐색하면서, 교점의 위치에서는 *을 아닌 곳에서는 .으로 문자열을 생성한 다음 print 수행

코드

use std::cmp::min;
use std::cmp::max;

fn main() {

    println!("sol 1");
    solution(vec![[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]);

    println!("sol 2");
    solution(vec![[0, 1, -1], [1, 0, -1], [1, 0, 1]]);

    println!("sol 3");
    solution(vec![[1, -1, 0], [2, -1, 0]]);

    println!("sol 4");
    solution(vec![[1, -1, 0], [2, -1, 0], [4, -1, 0]]);
    

}

fn solution(line: Vec<[i64;3]> ){

    let (mut max_x,mut min_x,mut max_y,mut min_y) = (i64::MIN, i64::MAX, i64::MIN, i64::MAX);

    let mut points: Vec<[i64;2]> = Vec::new();

    // 1. 입력으로 주어진 입력들의 모든 조합을 탐색
    for i in 0..line.len()-1 {
        for j in i+1..line.len(){
            // 2. 조합을 탐색하면서 두 직선간의 정수 교점을 찾아 리스트에 저장하며, 격자판의 필요 크기를 조정해 나아감
            let (a, b, e) = (line[i][0], line[i][1], line[i][2]);
            let (c, d, f) = (line[j][0], line[j][1], line[j][2]);

            let numerator_x = b*f - e*d;
            let numerator_y = e*c - a*f;
            let denominator = a*d - b*c;

            // 교점이 없는 경우 pass
            if denominator == 0{
                continue;
            }
			// 정수인 교점만을 골라내어 탐색
            if numerator_x % denominator == 0 && numerator_y % denominator == 0{

                let point: [i64;2] = [numerator_x/denominator, numerator_y/denominator];
                points.push(point);

                max_x = max(max_x, point[0]);
                min_x = min(min_x, point[0]);
                max_y = max(max_y, point[1]);
                min_y = min(min_y, point[1]);
            }
        }
    }

    // i64 => usize로 형변환. 격자판의 필요 크기를 구함
    let range_x:usize = (max_x - min_x +1).try_into().unwrap();
    let range_y:usize = (max_y - min_y +1).try_into().unwrap();

    // 격자판 생성
    // array는 compile 시에 size가 정해져 있어야 함으로, constant value가 아닌 값으로 생성 X. => 대신 vec 사용
    let mut is_pointed  = vec![vec![false;range_x] ; range_y];

    // 3. 격자판에 리스트에 저장된 교점들을 표시
    for point in points {
        let x: usize = (point[0]-min_x).try_into().unwrap();
        let y: usize = (max_y-point[1]).try_into().unwrap();
        is_pointed[y][x] = true;
    }

    
	// 정답 반환할 answer 리스트 생성
    let mut answer:Vec<String> =  Vec::with_capacity(range_y);

    // 4. 격자판을 탐색하면서, 교점의 위치에서는 `*`을 아닌 곳에서는 `.`으로 문자열을 생성한 다음 print 수행
    for row in is_pointed {
        let mut string_line = String::with_capacity(range_x);
        for col in row {
            if col {
                string_line.push_str("*");
            }else {
                string_line.push_str(".");
            }
        }
        answer.push(string_line);
    }
    
    for row in answer {
        println!("{}", row);
    }

} 

학습한 내용

1. Vec 선언 및 요소의 추가

   • Vec 선언의 3가지 방법

     • 빈 Vector 선언 (feat. 2차원)

       let mut vector: Vec<[i64;2]> = Vec::new(); // 2차원 선언

     • 값으로 선언

       let vector: Vec<[i64;3]> = vec![[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]; 

     • 배열의 용량 지정하며 선언

       let vector:Vec<String> =  Vec::with_capacity(n); // n 만큼의 배열 용량 미리 지정

       • capacity의 지정은 Vec의 길이(len)과는 상관 없으며, 단순히 memory에서의 공간은 n만큼 할당해 두는 것이다.
       • 다시 말해, vector의 용량을 n만큼 미리 확보해 둠으로써, n개의 요소까지는 vector에 추가되어도 메모리 재할당이 일어나지 않게 된다.

   • Vec에 요소 추가

     vector.push(element); // 요소 추가

2. array는 compile 시에 size가 정해져 있어야 함으로, constant value가 아닌 값으로 생성할 수 없다.

   • 위의 코드에서 2차원 배열을 선언할 때, 아래 코드를 사용시 컴파일 에러가 나게 된다.

     let range_x:usize = (max_x - min_x +1).try_into().unwrap();
     let range_y:usize = (max_y - min_y +1).try_into().unwrap();
     
     let mut is_pointed  = [[false;range_x] ; range_y]; // 컴파일 에러

3. indexing에는 usize 타입의 변수만 사용가능하면, 형변환에 사용되는 TryInto trait의 try_into() 가 사용된다.

   • TryInto 정의

     pub trait TryInto<T>: Sized {
         type Error;
     
         fn try_into(self) -> Result<T, Self::Error>;
     }

   • try_into는 self를 소비( consume)하기 때문에, try_into로 형변환시 더 이상 기존 변수는 사용할 수 없게 된다.

   • 또한 Result를 반환하기에 값을 얻고 싶다면 unwrap()을 사용해야 된다.