[프로그래머스][C++] 교점에 별 만들기
교점에 별 만들기
문제 링크
분석
Ax + By + C = 0의 형태로 n개의 직선이 주어집니다.
이 직선의 교점 중 정수 좌표에 별을 그리려고 합니다.
서로 다른 직선의 교점 중에서 x와 y가 정수인지 확인해주어 점을 표시하는 별을 그릴 수 있습니다.
격자의 크기는 2차원 배열로 별들을 표함하는 최소 크기이며, 별은 *, 격자는 .으로 채워주어 문자열 배열로 반환해야합니다.
최소 크기를 위해서는 모든 정수 교점의 x와 y값을 비교해 최소 및 최대 값을 찾아야합니다.
문제의 가장 밑에 참고 사항에 대해서 수학식으로 살펴보면 다음과 같습니다.
Ax + By + C = 0의 형태로 2개의 직선에 대해 교점을 구하기 위해서는 행렬식을 사용합니다.
주어진 모든 직선 쌍의 교점을 계산하는 방법은 다음과 같은 연립방정식으로 풀어 구할 수 있습니다.
두 직선 $( A_1x + B_1y + C_1 = 0 )$과 $( A_2x + B_2y + C_2 = 0 )$의 교점 $(x, y)$는 다음과 같이 연립방정식으로 구할 수 있습니다.
$A_1x + B_1y + C_1 = 0$
$A_2x + B_2y + C_2 = 0$
이 행렬 방정식을 풀면 $x$와 $y$를 구할 수 있습니다.
구할 수 있는 방법은 행렬식을 이용하는 방법입니다.
만약 $(A1 * B2) - (B1 * A2)$의 값이 0인 경우 두 직선은 평행하거나 일치한 경우입니다.
풀이
#include <string>
#include <vector>
#include <set>
#include <climits>
using namespace std;
vector<string> solution(vector<vector<int>> line) {
// 정수 교점을 저장할 집합으로, 중복을 제거하기 위해서 set을 사용한다.
set<pair<long long , long long>> points;
// 교점의 최소 / 최대 좌표를 저장하고, 격자의 범위를 결정한다.
long long minX = LLONG_MAX;
long long minY = LLONG_MAX;
long long maxX = LLONG_MIN;
long long maxY = LLONG_MIN;
// 모든 직선의 쌍에 대해서 반복한다.
for (int i = 0; i < line.size(); ++i)
{
long long A1 = line[i][0];
long long B1 = line[i][1];
long long C1 = line[i][2];
for (int j = 0; j < line.size(); ++j)
{
// 모든 직선 쌍에 대해 교점을 검사한다.
// 현재 코드에서는 i == j인 경우에도 검사하고, 평행하거나 같은 직선이기 때문에 continue 처리됩니다.
long long A2 = line[j][0];
long long B2 = line[j][1];
long long C2 = line[j][2];
// 두 직선의 교점을 구하기 위한 분모
long long denominator = (A1 * B2) - (B1 * A2);
// 분모가 0이면 평행하거나 같은 직선이므로 교점이 없다.
if (denominator == 0)
{
continue;
}
// 교점의 x, y 좌표를 계산하기 위한 분자를 구한다.
long long xNumerator = (B1 * C2) - (C1 * B2);
long long yNumerator = (C1 * A2) - (A1 * C2);
// 교점이 정수인지 확인한다.
if (xNumerator % denominator != 0 || yNumerator % denominator != 0)
{
continue;
}
// 정수 교점의 좌표를 계산하고 저장한다.
long long x = xNumerator / denominator;
long long y = yNumerator / denominator;
points.insert({x, y});
// 격자 범위를 계산하기 위해서 최소/최대 좌표를 갱신합니다.
minX = min(minX, x);
minY = min(minY, y);
maxX = max(maxX, x);
maxY = max(maxY, y);
}
}
// 격자의 너비와 높이를 계산합니다.
long long width = maxX - minX + 1;
long long height = maxY - minY + 1;
// '.' 문자로 초기화된 격자를 생성합니다.
vector<string> answer(height, string(width, '.'));
// 저장된 교점을 순회한다.
for (const auto& point : points)
{
// 좌표를 격자 기준으로 변환하고, 저장한다.
long long x = point.first - minX;
long long y = maxY - point.second;
answer[y][x] = '*';
}
return answer;
}
성능 요약
시간 복잡도는 $O(n^2 \ log \ n)$입니다.
- 모든 직선의 쌍에 대한 반복문 $n^2$
std::set의 삽입 연산 $n^2 \times log \ n$- 이 삽입 연산의 $n^2$은 최대 교점의 수입니다.
- 저장된 교점을 순회 $O(n^2)$
- $O(N^2) + O(N^2 log \ n +) + O(N^2)$
공간 복잡도는 $O(n^2)$입니다.
- 정수 교점을 저장하는
set<pair<long long , long long>> points$O(n^2)$ - 문자열 격자
vector<string> answer$O(n^2)$ - $O(n^2) + O(n^2)$
테스트 성능
테스트 1 〉 통과 (0.03ms, 3.67MB)
테스트 2 〉 통과 (0.49ms, 4.27MB)
테스트 3 〉 통과 (0.02ms, 4.08MB)
테스트 4 〉 통과 (0.75ms, 4.88MB)
테스트 5 〉 통과 (0.31ms, 4.03MB)
테스트 6 〉 통과 (0.10ms, 4.16MB)
테스트 7 〉 통과 (0.40ms, 4.14MB)
테스트 8 〉 통과 (0.02ms, 4.14MB)
테스트 9 〉 통과 (6.97ms, 4.13MB)
테스트 10 〉 통과 (6.23ms, 4.21MB)
테스트 11 〉 통과 (7.41ms, 4.02MB)
테스트 12 〉 통과 (8.75ms, 4.21MB)
테스트 13 〉 통과 (11.07ms, 4.2MB)
테스트 14 〉 통과 (7.80ms, 4.2MB)
테스트 15 〉 통과 (8.10ms, 4.2MB)
테스트 16 〉 통과 (10.22ms, 3.75MB)
테스트 17 〉 통과 (7.65ms, 4.21MB)
테스트 18 〉 통과 (8.77ms, 4.15MB)
테스트 19 〉 통과 (7.84ms, 4.13MB)
테스트 20 〉 통과 (7.02ms, 4.21MB)
테스트 21 〉 통과 (6.19ms, 4.46MB)
테스트 22 〉 통과 (0.01ms, 4.21MB)
테스트 23 〉 통과 (0.01ms, 4.14MB)
테스트 24 〉 통과 (0.01ms, 4.21MB)
테스트 25 〉 통과 (0.01ms, 4.21MB)
테스트 26 〉 통과 (0.01ms, 4.2MB)
테스트 27 〉 통과 (0.01ms, 4.14MB)
테스트 28 〉 통과 (0.01ms, 4.2MB)
테스트 29 〉 통과 (0.01ms, 4.19MB)
댓글남기기