교점에 별 만들기
[문제 Link] https://programmers.co.kr/learn/courses/30/lessons/87377
문제 설명
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 크기 이내에서 표현됩니다.
- 별이 한 개 이상 그려지는 입력만 주어집니다.
입출력 예
| 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인 경우 두 직선은 평행 또는 일치합니다.
로직
먼저 decimal 구조체를 사용한다. decimal 구조체를 사용할 경우 double보다 정확한 계산을 할 수 있다.
각 직선 별로 교차점을 구해야 한다. for문 2개를 통해 자기 자신이 아닌 직선과 비교하여 교점을 모두 구하여 list에 저장한다.
x의 최소값 최대값과 y의 최소값 최대값을 이용하여 별이 그려질 배열의 크기를 정한다.
크기를 정한 후에 좌표를 토대로 배열에 점을 찍는다.
전체 코드
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Solution
{
public static string[] solution(int[,] line) {
List<(long,long)> cross= new List<(long,long)>();
decimal px,py;
for(int i =0;i<line.GetLength(0);i++)
{
for(int j =0;j<line.GetLength(0); j++)
{
if (i != j)
{
long a1 = line[i,0];
long b1 = line[i,1];
long c1 = line[i,2];
long a2 = line[j,0];
long b2 = line[j,1];
long c2 = line[j,2];
long mod = a1*b2 -b1*a2;
if(mod == 0)
continue;
long demod1 = b1*c2 - c1*b2;
if(demod1%mod!=0) continue;
long demod2 = c1*a2 - a1*c2;
if(demod2%mod!=0) continue;
px = demod1/mod;
py = demod2/mod;
if(!cross.Contains(((long)px,(long)py)))
cross.Add(((long)px, (long)py));
}
}
}
long xMin = cross.Min(x =>x.Item1);
long xMax = cross.Max(x =>x.Item1);
long yMin = cross.Min(x=>x.Item2);
long yMax = cross.Max(x=>x.Item2);
long yIndex = yMax - yMin +1;
long xIndex = xMax - xMin +1;
for(int i =0;i<cross.Count();i++)
{
cross[i] = (cross[i].Item1-xMin,cross[i].Item2-yMin);
}
string[] answer = new string[yIndex];
string arr = "";
for(int i =0;i<yIndex;i++)
{
for(int j = 0;j<xIndex;j++)
{
if(cross.Contains((j,i)))
arr = arr +"*";
else
arr = arr + ".";
}
answer[yIndex-i-1] = arr;
arr = "";
}
return answer;
}
public static void Main(string[] args)
{
int[,] line0 = new int[,] {{2, -1, 4}, {-2, -1, 4}, {0, -1, 1}, {5, -8, -12}, {5, 8, 12}};
int[,] line1 = new int[,] {{0, 1, -1}, {1, 0, -1}, {1, 0, 1}};
int[,] line2 = new int[,] {{1, -1, 0}, {2, -1, 0}};
int[,] line3 = new int[,] {{1, -1, 0}, {2, -1, 0}, {4, -1, 0}};
string[] results0 = solution(line0);
foreach(var row in results0)
Console.WriteLine(row);
}
}
결과
