본문 바로가기

# 02/Swift - CTP

[Swift] 코딩테스트 연습! Lv2. 교점에 별 만들기

반응형
/* 교점에 별 만들기
 
 - Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.
 
 예를 들어, 다음과 같은 직선 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)입니다.

 만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.
 위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.
 "..........."
 ".....*....."
 "..........."
 "..........."
 ".*.......*."
 "..........."
 "..........."
 "..........."
 "..........."
 ".*.......*."
 "..........."
 이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

 따라서 정답은

 "....*...."
 "........."
 "........."
 "*.......*"
 "........."
 "........."
 "........."
 "........."
 "*.......*"
 입니다.

 직선 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 크기 이내에서 표현됩니다.
 별이 한 개 이상 그려지는 입력만 주어집니다.
*/
func getSpot(a:Int, b:Int, c:Int, d:Int, e:Int, f:Int) -> [Int] {
    if (b*f-e*d)%(a*d-b*c) == 0 && (e*c-a*f)%(a*d-b*c) == 0 {
        return [(b*f-e*d)/(a*d-b*c), (e*c-a*f)/(a*d-b*c)]
    } else {
        return []
    }
}

func solution6(_ line:[[Int]]) -> [String] {
    var spots = Set<[Int]>()
    for i in 0...line.count-2 {
        for j in 1...line.count-1-i {
            if line[i][0]*line[i+j][1] - line[i][1]*line[i+j][0] != 0 {
                var spot = getSpot(a: line[i][0], b: line[i][1], c: line[i+j][0], d: line[i+j][1], e: line[i][2], f: line[i+j][2])
                if spot.count > 0 {
                    spots.insert(spot)
                }
            }
        }
    }
    var maxX:Int = spots.first![0]
    var minX:Int = spots.first![0]
    var maxY:Int = spots.first![1]
    var minY:Int = spots.first![1]
    spots.map {
        maxX = max($0[0], maxX)
        minX = min($0[0], minX)
        maxY = max($0[1], maxY)
        minY = min($0[1], minY)
    }
    var result:[String] = []
    for i in minY...maxY {
        var list = spots.filter { $0[1] == i }.map { $0[0] }
        if list.count > 0 {
            var str = ""
            for j in minX...maxX {
                if list.contains(j) {
                    str += "*"
                } else {
                    str += "."
                }
            }
            result.insert(str, at: 0)
        } else {
            result.insert(String(repeating: ".", count: maxX-minX+1), at: 0)
        }
    }
    return result
}
반응형