문제 설명
Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.
예를 들어, 다음과 같은 직선 5개를
2x - y + 4 = 0-2x - y + 4 = 0-y + 1 = 05x - 8y - 12 = 05x + 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 크기 이내에서 표현됩니다.
- 별이 한 개 이상 그려지는 입력만 주어집니다.
입출력 예
| line | result |
|---|---|
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] |
["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] |
[[0, 1, -1], [1, 0, -1], [1, 0, 1]] |
["*.*"] |
[[1, -1, 0], [2, -1, 0]] |
["*"] |
[[1, -1, 0], [2, -1, 0], [4, -1, 0]] |
["*"] |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
직선 y = 1, x = 1, x = -1는 다음과 같습니다.
(-1, 1), (1, 1) 에서 교점이 발생합니다.
따라서 정답은
"*.*"
입니다.
입출력 예 #3
직선 y = x, y = 2x는 다음과 같습니다.
(0, 0) 에서 교점이 발생합니다.
따라서 정답은
"*"
입니다.
입출력 예 #4
직선 y = x, y = 2x, y = 4x는 다음과 같습니다.
(0, 0) 에서 교점이 발생합니다.
따라서 정답은
"*"
입니다.
참고 사항
Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.
또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
문제 풀이
문제 접근
1. 점들을 하나씩 비교하기
for i in range(len(line)): for j in range(i+1, len(line)):
line이 1, 2, 3, 4, 5라고 하면,
1일 경우 2, 3, 4, 5
2일 경우 3, 4, 5 를 비교할 수 있습니다.
2. 평행하지 않으면서 교점이 자연수인가?
if tmp != 0 and (B*F-E*D)%tmp == 0 and (E*C-A*F)%tmp == 0:
tmp는 문제의 조건과 같이 AD - BC 입니다.
tmp가 0이 아니라면 평행하다는 조건에 부합합니다.
또한 교점이 자연수인지 비교는 tmp를 나누고 나머지가 0인지 비교를 하였습니다.
3. 칸 만들기
answer = [["." for c in range(maxX-minX+1)] for r in range(maxY-minY+1)]
(2,3) (1,5) (3,2)가 교점이라고 해보겠습니다.
x의 최솟값은 1, x의 최댓값은 3
y의 최솟값은 2, y의 최댓값은 5 입니다.
문제에 해당하는 프레임을 작성하기 위해서는
최댓값 - 최솟값 + 1을 해주면 됩니다.
따라서 x는 (3 - 1 + 1)인 3이고
y는 (5 - 2 + 1)인 4입니다.
4. 그래프와 컴퓨터 좌표의 차이
answer[maxY-y][x-minX] = "*"
컴퓨터에서 그래프를 그릴 때는 수학적 좌표계와 달리 y축이 반대로 되어 있습니다. 따라서 수학적 좌표계에서 점을 찍으려면 y좌표를 반전시켜야 합니다.
이 때문에 y좌표 = maxY - y라는 공식을 사용합니다. 여기서 maxY는 화면의 높이를 의미하며, 이를 통해 위쪽에서 아래쪽으로 증가하는 y값을 아래쪽에서 위쪽으로 증가하는 값으로 변환합니다.
전체 코드
def solution(line):
points = set()
maxX, maxY, minX, minY = -10e10, -10e10, 10e10, 10e10
for i in range(len(line)):
for j in range(i+1, len(line)):
A, B, E = line[i]
C, D, F = line[j]
tmp = A * D - B * C
if tmp != 0 and (B*F-E*D)%tmp == 0 and (E*C-A*F)%tmp == 0:
X, Y = (B*F-E*D)//tmp, (E*C-A*F)//tmp
maxX, maxY, minX, minY = max(maxX, X), max(maxY, Y), min(minX, X), min(minY, Y)
points.add((X, Y))
answer = [["." for c in range(maxX-minX+1)] for r in range(maxY-minY+1)]
for x, y in points:
answer[maxY-y][x-minX] = "*"
return ["".join(row) for row in answer]