[Programmers 위클리 챌린지 10주차] 교점에 별 만들기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/87377

코딩테스트 연습 - 10주차

최대 10,000이므로 곱할 경우 int의 범위를 벗어날 수 있습니다.

이 때문에 27, 28번 시스템 케이스에서 계속 시간 초과가 나서 상당히 애를 먹었습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 교점 공식을 통해 정수 교점들을 벡터에 넣어줍니다.

1.1 이 때, 최소 사각형을 만들기 위해 x와 y의 최대 최소 값 또한 구해줍니다.

2. 1.1에서 구한 값을 통해 모두 '.'으로 구성된 최소 사각형을 만들어줍니다.

3. 2번에서 만들어준 최소 사각형에 1번에서 구한 교점들에 '*'로 표시해줍니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <climits>
	using namespace std;
	vector<string> solution(vector<vector<int>> line) {
	long long minX = LLONG_MAX, minY = LLONG_MAX;
	long long maxX = LLONG_MIN, maxY = LLONG_MIN;
	vector<pair<long long, long long>> coords;
	int lineSize = line.size();
	for (int i = 0; i < lineSize; i++)
	{
	for (int j = i + 1; j < lineSize; j++)
	{
	long long A = line[i][0], B = line[i][1], E = line[i][2];
	long long C = line[j][0], D = line[j][1], F = line[j][2];
	long long xNumerator = B * F * 1LL - E * D * 1LL;
	long long yNumerator = E * C * 1LL - A * F * 1LL;
	long long mod = A * D * 1LL - B * C * 1LL;
	if (mod == 0)
	{
	continue;
	}
	if (xNumerator % mod || yNumerator % mod)
	{
	continue;
	}
	long long x = xNumerator / mod;
	long long y = yNumerator / mod;
	minX = min(minX, x);
	minY = min(minY, y);
	maxX = max(maxX, x);
	maxY = max(maxY, y);
	coords.push_back({ x, y });
	}
	}
	string row = string(maxX - minX + 1, '.');
	vector<string> answer(maxY - minY + 1, row);
	for (pair<long long, long long> coord : coords)
	{
	answer[abs(coord.second - maxY)][abs(coord.first - minX)] = '*';
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~