[프로그래머스] 교점에 별 만들기 with Swift

• 위클리 챌린지
• 교점에 별 만들기
• Level 2

 

문제

• Ax + By + C = 0 으로 표현할 수 있는 n 개의 직선이 주어짐
• 이 직선의 교점 중 정수 좌표에 별을 그리려고 함

 

• line 길이(직선의 개수)는 2 이상 1,000 이하
• line은 [A, B, C] 배열
• A, B, C는 -100,000 이상 100,000 이하 정수
• 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않음
• A = 0 이면서 B = 0 인 경우는 주어지지 않음
• 정답은 1000*1000 크기 내로 표현됨
• 별이 한 개 이상 그려지는 입력만 주어짐

참고.
Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 발생하는 경우, 교점은 다음과 같음(아래 이미지 참고)
또한 AD - BC = 0 인 경우 두 직선은 평행 또는 일치함

 

예. 5개의 직선

• 2x - y + 4 = 0
• -2x - y + 4 = 0
• -y + 1 = 0
• 5x - 8y - 12 = 0
• 5x + 8y + 12 = 0

 

좌표 상에 그리면 다음과 같이 됨

 

이때 발생하는 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)인데 그중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)

 

해당 좌표에 별을 그리면 다음 그림과 같이 되며, 이것을 별은 *, 그 외는 . 으로 표현하여 반환하려 함

"..........."
".....*....."
"..........."
"..........."
".*.......*."
"..........."
"..........."
"..........."
"..........."
".*.......*."
"..........."

 

• 이때 격자판의 최대 범위는 모든 별을 포함하는 최소 크기로만 그리면 됨
• 따라서 정답은 다음과 같음. 각 문자열을 배열에 담아 반환하면 됨

"....*...."
"........."
"........."
"*.......*"
"........."
"........."
"........."
"........."
"*.......*"

 

Idea

• 먼저 모든 직선 쌍 사이에 발생하는 교점을 구하기
• 교점 중 정수로만 이루어진 교점만 포함하며,  AD - BC = 0 인 경우 또한 제외함
• y값 최소, 최대 값을 구하고, x값 최소, 최대 값을 구하고 해당 범위 내에 별 찍기

 

Code

Swift

 

처음 작성한 코드

• x와 y의 최대, 최소 값은 교점을 구할 때 구해도 되지만 아래 구현은 교점을 모두 구한 뒤 정렬하여 구하도록 하였음
• 교점이 정수인지 판단하는 방법은 정수로 만든 값과 계산된 값에 각각에 10의 배수를 곱하여 서로 비교 후 판단할 수 있으나 소수점이 어떻게 나오느냐에 따라 올바른 판단이 되지 않을 수 있음
• 따라서 정수의 나머지 연산을 이용하여 나누어 떨어지는 경우를 정수로 처리하도록 수정

 

• 또한 동일한 교점이 여러 개 나올 수 있기 때문에 집합으로 한 번 변경해주었음 (이 과정은 굳이 할 필요는 없으나 중복되는 값이 많아지는 경우 유용할 것으로 보임)
• 처음엔 x 값 기준으로 정렬하여 처음 값과 마지막 값을 가져와 최대, 최소 값을 구하였고
• 그다음엔 y 값 기준(큰 값 → 작은 값), 동일한 경우는 x 값 기준(작은 값 → 큰 값)으로 정렬하여 구함

(처음엔 x 값이 정렬되어 있어야 차례로 별을 찍을 수 있을 듯하여 정렬하였는데 이후 배열을 사용하여 해당 위치에 별을 찍도록 해서 굳이 할 필요는 없을 듯함)

→ 이걸 쓰다가… 전부 정렬할 필요가 없다는 것을 깨달음. 대신 교점 구할 때 최대, 최솟값 구해야 함

• 아무튼... y의 최대부터 최소까지 반복을 하다가 교점이 있는 y가 나타나면 해당 y 줄에 포함된 x에 별을 찍음
• 배열에 별을 찍을 때 교점과 인덱스 사이에서 조정을 해줘야 함

import Foundation

func solution_1(_ line:[[Int]]) -> [String] {
    
    var points: [[Int]] = []
    for i in 0..<line.count-1 {
        let (a, b, e) = (line[i][0], line[i][1], line[i][2])
        for j in i+1..<line.count {
            let (c, d, f) = (line[j][0], line[j][1], line[j][2])
            
            let parent = a*d - b*c
            let x_child = b*f - e*d
            let y_child = e*c - a*f
            if parent == 0 { continue }
            if x_child % parent == 0 && y_child % parent == 0 {
                let x = x_child / parent
                let y = y_child / parent
                points.append([x, y])
            }
        }
    }
    points = Array(Set(points))
    points.sort { $0[0] < $1[0] }
    let (min_x, max_x) = (points[0][0], points[points.count-1][0])
    points.sort { 
        if $0[1] == $1[1] {
            return $0[0] < $1[0]
        }
        return $0[1] > $1[1]
    }
    let (min_y, max_y) = (points[points.count-1][1], points[0][1])
    
    var answer: [String] = []
    for y in (min_y...max_y).reversed() {
        var x = Array(repeating: ".", count: max_x - min_x + 1)
        while !points.isEmpty, points[0][1] == y {
            let p = points.removeFirst()
            let index = p[0] + min_x * -1
            x[index] = "*"
        }
        
        answer.append(x.joined(separator: ""))
    }
    
    return answer
}

 

수정한 버전의 코드

위의 설명을 쓰다가 정렬하지 않고도 별을 찍는데 지장이 없다는 것을 깨닫고 다음과 같이 수정함

• 교점을 구하는 과정에서 각 교점의 최대, 최소 값을 구하도록 변경
• 정렬하는 과정을 제거
• 전체 좌표 판에 대한 배열을 “.” 으로 초기화하여 만든 후
• 각 교점에 대한 값을 index 위치로 조정한 후 해당 위치에 별 찍기

 

x 값의 경우, 작은 값에서 큰 값으로 인덱스가 설정되므로 cur_x - min_x

예. -3 ~ 4 → x- 최소 값 → 0 ~ 7

y 값의 경우, 큰 값에서 작은 값으로 인덱스가 설정되므로 max_y - cur_y

예. 5 ~ -3 → 최대 값 - y → 0 ~ 8

import Foundation

func solution_2(_ line:[[Int]]) -> [String] {
    
    var points: [[Int]] = []
    var max_x = Int.min, max_y = Int.min
    var min_x = Int.max, min_y = Int.max
    for i in 0..<line.count-1 {
        let (a, b, e) = (line[i][0], line[i][1], line[i][2])
        for j in i+1..<line.count {
            let (c, d, f) = (line[j][0], line[j][1], line[j][2])
            
            let parent = a*d - b*c
            let x_child = b*f - e*d
            let y_child = e*c - a*f
            if parent == 0 { continue }
            if x_child % parent == 0 && y_child % parent == 0 {
                let x = x_child / parent
                let y = y_child / parent
                points.append([x, y])
                
                max_x = max(max_x, x)
                min_x = min(min_x, x)
                max_y = max(max_y, y)
                min_y = min(min_y, y)
            }
        }
    }
    points = Array(Set(points))
    
    var coordinate = Array(repeating: Array(repeating: ".", count: max_x - min_x + 1), count: max_y - min_y + 1)
    for p in points {
        let x = p[0] + min_x * -1
        let y = max_y - p[1]
        coordinate[y][x] = "*"
    }
    
    var answer: [String] = []
    for row in coordinate {
        answer.append(row.joined(separator: ""))
    }
    
    return answer
}