[programmers/Swift] 교점에 별 만들기

programmers.co.kr - 코딩테스트연습 - Lv.2 - 위클리 챌린지 - 교점에 별 만들기

코딩테스트 연습 - 교점에 별 만들기

Constraints :

• 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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/05/18.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ line:[[Int]]) -> [String] {
    var coordinates = [Int: [Int]]()
    var maxX = Int.min, maxY = Int.min, minX = Int.max, minY = Int.max
    
    
    func makeCoordinates(arr1: [Double], arr2: [Double]) {
        let deno = arr1[0] * arr2[1] - arr1[1] * arr2[0]
        guard deno != 0 else { return }
        
        let x = (arr1[1]*arr2[2] - arr1[2]*arr2[1]) / deno
        let intX = Int(x)
        guard x == Double(intX) else { return }
    
        
        let y = (arr1[2]*arr2[0] - arr1[0]*arr2[2]) / deno
        let intY = Int(y)
        guard y == Double(intY) else { return }
        
        maxX = max(maxX, intX)
        minX = min(minX, intX)
        maxY = max(maxY, intY)
        minY = min(minY, intY)
        
        if let _ = coordinates[intY] {
            coordinates[intY]?.append(intX)
        } else {
            coordinates.updateValue([intX], forKey: intY)
        }
    }
    
    func combination(_ arr: [[Double]], size: Int, current index: Int, selected: [[Double]]) {
        if size == 0 {
            makeCoordinates(arr1: selected[0], arr2: selected[1])
        } else if index == arr.count {
            return
        } else {
            var newSelected = selected
            newSelected.append(arr[index])
            combination(arr, size: size - 1, current: index + 1, selected: newSelected)
            combination(arr, size: size, current: index + 1, selected: selected)
        }
    }

    combination(line.map { $0.map { Double($0) } }, size: 2, current: 0, selected: [])
    
    var results = [String]()
    for y in (minY...maxY).reversed() {
        var line = [String](repeating: ".", count: maxX - minX + 1)
        if let xArr = coordinates[y] {
            for x in xArr {
                line[x - minX] = "*"
            }
        }
        results.append(line.joined())
    }
    
    return results
}

print(solution([[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]))
// ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
print(solution([[0, 1, -1], [1, 0, -1], [1, 0, 1]]))  // ["*.*"]
print(solution([[1, -1, 0], [2, -1, 0]]))  // ["*"]
print(solution([[1, -1, 0], [2, -1, 0], [4, -1, 0]]))  // ["*"]

How I tried this :
시간초과를 걱정했지만 다행히 통과되었다.

순열을 이용해서 모든 직선을 2개씩 묶고, 묶인 직선간에 정수 교점을 찾아서 딕셔너리에 넣었다.

딕셔너리로 넣은 이유는 key 값으로 y 좌표에 쉽게 접근해서 x 좌표를 얻으려고 했다.

실제좌표가 저장되기 때문에 minX 값을 빼서 minX가 0좌표가 되도록 만들었다.

 

사실 이 풀이가 안되면.. 큰일 날뻔했다..

더 좋은 풀이가 있을거 같긴하지만... 직관적으로 풀어보았다.

 

문제에 관한 모든 저작권 : https://programmers.co.kr/