프로그래머스 위클리 챌린지10주차 교점에 별 만들기

1.  문제 링크

https://programmers.co.kr/learn/courses/30/lessons/87377

코딩테스트 연습 - 10주차

 

 

2.  풀이

 

직선은 서로 평행하거나 일치하거나 한 점에서 만난다. 이 3가지 경우 말고는 없다.

문제에서는 두 직선에 대한 교점을 구하는 식 / 기울기가 같은 경우를 판단하는 방법을 알려줬다. 또한, 두 직선이 완전히 일치하는 경우는 없고 모든 교점은 1000*1000의 배열 내에 있다는 조건을 줬다.

 

대략적인 풀이는 아래와 같다.

 

1. 모든 직선을 비교하면서 주어진 공식을 통해 교점을 구한다.(O(n^2))
2. 교점에서 xMin, yMin, xMax, yMax를 구해서 교점을 표현할 배열의 범위를 결정한다.
3. 범위에 맞게 배열을 만들고 초기 값을 '.'으로 한다.
4. 교점의 위치에  '*'을 대입해 준다.
   
   1. 배열의 (0,0)값은 실제 교점에서 (xMin, yMax) 값임을 유의하여 상대적인 교점 위치를 배열에 대입해 줘야 한다.

 

//1) 교점들 다 구해서 저장	=> O(N^2)
//2) (0,0) 기준점 정하기 => {x축 min, y축 min}
//3) (끝,끝) 기준점 정하기 => {x축 max, y축 max}
//4) 답 구하기

#include <string>
#include <vector>
#include <set>
#include <limits>

using namespace std;

class Pos {
public:
	long long x, y;
	Pos() {};
	Pos(const long long& x, const long long& y) {
		this->x = x;
		this->y = y;
	}

	bool operator<(const Pos& p1)const  {
		if (p1.x == this->x)
			return p1.y < this->y;
		return p1.x < this->x;
	}
};

set<Pos>			meetingPosSet;
vector<string>		answer;


void init() {
	meetingPosSet.clear();
	answer.clear();
}

long long GetDenominator(const vector<long long>& line1, const vector<long long>& line2) {
	return (line1[0] * line2[1]) - (line1[1] * line2[0]);
}

long long GetLeftMolecules(const vector<long long>& line1, const vector<long long>& line2) {
	return (line1[1] * line2[2]) - (line1[2] * line2[1]);
}

long long GetRightMolecules(const vector<long long>& line1, const vector<long long>& line2) {
	return (line1[2] * line2[0]) - (line1[0] * line2[2]);
}

void GetMeetingPos(const vector<long long>& line1, const vector<long long>& line2) {
	long long denominator = GetDenominator( line1,line2 );
	if (denominator == 0)
		return;
	long long leftMolecules = GetLeftMolecules(line1, line2);
	if (leftMolecules % denominator != 0)
		return;
	long long rightMolecules = GetRightMolecules(line1, line2);
	if (rightMolecules % denominator != 0)
		return;
	meetingPosSet.insert(Pos{ leftMolecules / denominator , rightMolecules / denominator });
}


vector<string> solution(vector<vector<int>> line) {
	init();

	for (int i = 0; i < line.size(); i++) {
		for (int j = i + 1; j < line.size(); j++) {
			GetMeetingPos({ (long long)line[i][0], (long long)line[i][1],(long long)line[i][2] }, { (long long)line[j][0], (long long)line[j][1],(long long)line[j][2] });
		}
	}

	long long xmin = numeric_limits<long long>::max(), xmax = -1* numeric_limits<long long>::max();
	long long ymin = numeric_limits<long long>::max(), ymax = -1* numeric_limits<long long>::max();

	for (Pos p : meetingPosSet) {
		xmin = xmin < p.x ? xmin: p.x;
		xmax = xmax > p.x ? xmax : p.x;
		ymin = ymin < p.y ? ymin : p.y;
		ymax = ymax > p.y ? ymax : p.y;
	}

	long long xLen = xmax - xmin + 1;
	long long yLen = ymax - ymin + 1;
	
	for (int i = 0; i < yLen; i++) {
		string tmp = "";
		for (int j = 0; j < xLen; j++) {
			tmp.push_back('.');
		}
		answer.push_back(tmp);
	}
	
	for (Pos p : meetingPosSet) 
		answer[ymax - p.y][p.x - xmin] = '*';

	return answer;
}