[Programmers] 위클리 챌린지 교점에 별만들기 (python)

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

어려웠다 ..

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

문제 맨 아래의 참고사항을 안보고 풀다가 낭패 ;; 꼭 확인하기..

문제 설명

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)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.

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

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

따라서 정답은

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

참고사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

소스코드

def solution(line):
    INF = 1e9
    mark = []
    minx, maxx, miny, maxy = INF, -INF, INF, -INF
    for i in range(len(line)):
        for j in range(i+1,len(line)):
            A,B,E = line[i]
            C,D,F = line[j]
            mo = A*D-B*C
            if mo != 0: ## 두 직선이 평행하거나 일치하지 않을때
                x = (B*F-E*D)/mo
                y = (E*C-A*F)/mo
            if x == int(x) and y == int(y): ## 소수점 있는 경우 제외
                x,y=int(x),int(y)
                minx,maxx,miny,maxy = min(minx,x),max(maxx,x),min(miny,y),max(maxy,y)
                mark.append((x,y))
    res=[['.' for _ in range(maxx-minx+1)] for _ in range(maxy-miny+1)]
    for x,y in mark : 
        res[maxy-y][x-minx] = '*'
    return [''.join(s) for s in res]

별 찍힌 리스트까지 만들고 이를 출력하는데 애를 먹었느데

.join() 함수를 이용해 리스트를 문자열로 변환하였다

https://blockdmask.tistory.com/468

[python] 파이썬 join 함수 정리 및 예제 (문자열 합치기)