You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Ax + By + C = 0으로 표현할 수 있는 n개의 직선 정보 line이 주어지고, 각 원소는 (A, B, C) 형태이다.
n개의 직선의 모든 교점의 좌표를 포함하는 최소한의 사각형 크기를 구하라
2 <= n <= 1000
-100,000 <= A, B, C <= 100, 000
A=0이면서 B=0인 경우는 없다.
별이 1개 이상 그려지는 입력만 주어진다.
아이디어
주어진 직선들의 모든 교점 찾기 (정수로 표현되는 교점만)
먼저 모든 직선 쌍에 대해 반복해 교점의 좌표를 구해야 한다.
두 직선이 Ax + By + E = 0, Cx + Dy + F = 0 일 때
이 때, AD - BC = 0인 경우는 평행 또는 일치하는 직선이기 때문에 제외한다.
두 직선의 교점을 아래 공식을 참조해 구한다.
이 때, 정수인 교점만 사용한다.
교점들의 최대 x, 최소 x, 최대 y, 최소 y 값 찾아서 사각형의 최소 크기로 나타내기
교점 하나씩 꺼내 비교하면서 표현해야 할 사각형의 최소 크기를 구한다.
즉, 가로 길이는 (최대 x - 최대 x)로 세로 길이는 (최대 y - 최소 y)로 구해서 사각형 2차원 배열을 생성한다.
2중 for 문으로 사각형 배열을 돌면서 해당하는 위치에 "*"를 찍어야 한다.
이 때 배열은 (0, 0)부터 시작하기 때문에 사분면 위의 좌표를 (0, 0) 부터 시작하는 배열을 기준으로 변환해야 한다.
(0, 0)의 기준을 (minX, maxY) 기준으로 바꿔야 하는 것이다.
x축 좌표의 경우 사분면 상의 x좌표가 음수가 되지 않도록 사분면 상의 x좌표에 최소 x값을 빼준다.
y축 좌표의 경우 2차원 배열에서는 y축 방향이 반대이니까 최대 y값에서 사분면 상의 y좌표를 빼준다.
시간 복잡도
모든 직선의 쌍에 대해 반복하는데 걸리는 시간은 O(n^2), 교점 리스트를 반복하는데 걸리는 시간은 직선 n개에서 최대 n(n-1)/2개의 교점이 나올 수 있으므로 O(n^2)이다.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
교점에 별 만들기 - Level 2
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87377
문제 설명
Ax + By + C = 0으로 표현할 수 있는 n개의 직선 정보 line이 주어지고, 각 원소는 (A, B, C) 형태이다.아이디어
먼저 모든 직선 쌍에 대해 반복해 교점의 좌표를 구해야 한다.
두 직선이
Ax + By + E = 0,Cx + Dy + F = 0일 때이 때, AD - BC = 0인 경우는 평행 또는 일치하는 직선이기 때문에 제외한다.
두 직선의 교점을 아래 공식을 참조해 구한다.
이 때, 정수인 교점만 사용한다.
교점 하나씩 꺼내 비교하면서 표현해야 할 사각형의 최소 크기를 구한다.
즉, 가로 길이는 (최대 x - 최대 x)로 세로 길이는 (최대 y - 최소 y)로 구해서 사각형 2차원 배열을 생성한다.
2중 for 문으로 사각형 배열을 돌면서 해당하는 위치에 "*"를 찍어야 한다.
이 때 배열은 (0, 0)부터 시작하기 때문에 사분면 위의 좌표를 (0, 0) 부터 시작하는 배열을 기준으로 변환해야 한다.
(0, 0)의 기준을 (minX, maxY) 기준으로 바꿔야 하는 것이다.
시간 복잡도
모든 직선의 쌍에 대해 반복하는데 걸리는 시간은 O(n^2), 교점 리스트를 반복하는데 걸리는 시간은 직선 n개에서 최대 n(n-1)/2개의 교점이 나올 수 있으므로 O(n^2)이다.
구현
All reactions