[Python] programmers 교점에 별 만들기

1. 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/87377

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

2. 문제 요약

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

 

3. 아이디어 정리

1. 이중 for문을 돌려 선 2개를 선택한다.
2. 평행 또는 일치하는 경우 continue
3. x, y 값이 정수가 아닌 경우 continue
4. 2, 3번 통과하면 x,y 점을 추가하고 최대 x, y 최소 x, y 값 경신을 진행한다.
5. 좌표를 그려준다.

 

4. 문제 풀이

4-1. 내 풀이

def solution(line):
    INF = float('inf')
    points = list()
    max_x = -INF
    min_x = INF
    max_y = -INF
    min_y = INF
    for i, l1 in enumerate(line):
        for j, l2 in enumerate(line[i+1:]):
            a, b, e = l1
            c, d, f = l2
            m = a * d - b * c
            if m == 0:   # 평행 또는 일치
                continue
            if (b * f - e * d) % m !=0 or (e * c - a * f) % m !=0:   # 정수인지 확인(나머지가 없어야함!)
                continue

            x = (b * f - e * d) / m
            y = (e * c - a * f) / m
            x, y = int(x), int(y)
            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)

    answer = [['.'] * (max_x - min_x + 1) for _ in range(max_y - min_y + 1)]
    for x, y in points:
        answer[max_y - y][x - min_x] = "*"

    return [''.join(l) for l in answer]

 

 

5. 결론

• 구현