[Swift] 프로그래머스 위클리 챌린지 교점에 별 만들기



Problem

 

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

---

Solution

 

해당 문제의 핵심은 두 직선(방정식)의 교점을 찾는 방법을 아는 것입니다.

 

아래 두 직선이 있다고 가정하겠습니다.

 

1. ax + by + c
2. dx + ey + f

 

교점을 찾는 식은 아래와 같습니다.

 

x = (bf - ed) / (ad - bc)
y = (ec - af) / (ad - bc)

 

여기서 ad - bc가 만약 0이라면 두 직선은 평행하다는 의미입니다.

 

위 방식대로 모든 직선의 교점을 찾으며 x의 가장 큰 값과 작은 값, y의 가장 큰 값과 작은 값을 찾아 최소 사각형의 범위를 정합니다.

 

마지막으로 범위 안에서 교점의 위치를 별로 바꿔준 뒤 반환합니다.

 

코드 해설

 

교점,최소 사각형,직선의 구조체를 만들어줍니다.

 

struct Line {
    let x:Int,y:Int,c:Int
}

struct Square {
    var minX:Int = Int.max
    var maxX:Int = -Int.max
    var minY:Int = Int.max
    var maxY:Int = -Int.max
}

struct Meet {
    let x:Int,y:Int
}

 

1. 교점을 찾는다.

 

위에서 교점을 구하는 식으로 두 직선의 교점을 구해줍니다.

 

다만 문제에서 x와 y 모두 정수인 교점만 필요하므로 정수가 아닌 것은 nil로 반환합니다.

 

func findMeet(_ l1:Line,_ l2:Line) -> Meet? {
    let adbc = l1.x*l2.y - l1.y*l2.x
    if adbc == 0 { return nil }
    let bfed = l1.y*l2.c - l1.c*l2.y
    let ecaf = l1.c*l2.x - l1.x*l2.c
    let meet = Meet(x:bfed/adbc, y:ecaf/adbc)
    return bfed % adbc == 0 && ecaf % adbc == 0 ? meet : nil
}

 

2. 모든 직선의 교점을 구한다.

 

모든 직선의 교점을 찾아 저장합니다.

 

func getIntegerMeet(lines:[[Int]]) -> [Meet] {
    var lines:[[Int]] = lines
    var meets:[Meet] = []
    while !lines.isEmpty {
        let first = lines.removeFirst()
        let firstLine = Line(x:first[0], y:first[1], c: first[2])
        for l in lines {
            let otherLine = Line(x: l[0], y: l[1], c: l[2])
            if let meet = findMeet(firstLine,otherLine) {
                meets.append(meet)
            }
        }
    }
    return meets
}

 

3. 모든 교점들을 이용해 최소 사각형의 범위를 정한다.

 

func getSquare(meets:[Meet]) -> Square {
    var square:Square = Square()
    meets.forEach {
        square.minX = min(square.minX,$0.x)
        square.maxX = max(square.maxX,$0.x)
        square.minY = min(square.minY,$0.y)
        square.maxY = max(square.maxY,$0.y)
    }
    return square
}

 

4. 최소 사각형에 교점을 별로 바꿔준다.

 

x의 최대값 - 최소값 + 1만큼의 배열을 y의 최댓값 - 최소값 + 1만큼 만들어줍니다.

 

그 다음 교점들을 확인하면서 별로 바꿔줍니다.

 

주의하실 점은 좌표에서 y값은 위로 갈수록 커지기 때문에 최댓값에서 현재 y값을 빼줍니다.

 

func changeMeetsToStar(meets:[Meet],square:Square) -> [String] {
    var sqaureDot = Array(repeating: Array(repeating: ".", count: square.maxX-square.minX+1), count: square.maxY-square.minY+1)
    for meet in meets {
        let x = meet.x - square.minX
        let y = square.maxY - meet.y
        sqaureDot[y][x] = "*"
    }
    return sqaureDot.map{$0.joined()}
}

 

5. 별로 바꾼 사각형을 반환한다.

 

func solution(_ line:[[Int]]) -> [String] {
    let meets:[Meet] = getIntegerMeet(lines:line)
    let square = getSquare(meets: meets)
    return changeMeetsToStar(meets: meets, square: square)
}

---

Source Code