<div id="readability-page-1" class="page"><div><img src="https://velog.velcdn.com/images/psj0810/post/4bff9161-8fa0-4e18-8ce1-f91c210dace2/image.png"> 
<img src="https://velog.velcdn.com/images/psj0810/post/0e777b35-172e-4bde-8cc3-0585fa2ae3a7/image.png"> 
<img src="https://velog.velcdn.com/images/psj0810/post/1be3a7c7-02dd-47df-95d0-7bf7708cfb02/image.png"> 
<img src="https://velog.velcdn.com/images/psj0810/post/2deffb3e-bc61-401f-abf1-b5135efafe6e/image.png"> 
<img src="https://velog.velcdn.com/images/psj0810/post/5ea916fa-8dba-4dc2-b06b-811b5bb1d60a/image.png"> 
<img src="https://velog.velcdn.com/images/psj0810/post/fe912c04-fb19-45b8-8ca0-5c800510f000/image.png"> 
<img src="https://velog.velcdn.com/images/psj0810/post/3f5a5d08-78ee-4d2b-98c1-d3a9493c3e81/image.png">
<blockquote>
문제 풀이 흐름
<ol>
<li>모든 직선 쌍에 대해 반복 
A. 교점 좌표 구하기 
B. 정수 좌표만 저장</li>
<li>저장된 정수들에 대해 x,y 좌표의 최대값, 최소값구하기</li>
<li>구한 최대값, 최솟값을 이용하여 2차원 배열의 크기 결정</li>
<li>2차원 배열에 별 표시</li>
<li>문자열 배열로 변환 후 반환</li>
</ol>
</blockquote>
좌표를 표현해야하니 좌표를 나타내는 클래스를 만든다
<pre><code>class Point{
 long x;
 long y;

 Point(long x, long y){
 this.x = x;
 this.y = y;
 }
}</code></pre>
<img src="https://velog.velcdn.com/images/psj0810/post/7bebaba7-3b25-4e3f-a0ec-d5f32c023572/image.png">
<ul>
<li>무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.</li>
</ul>
위 제한사항에서 직선 하나는 직선 하나와만 교차한다는 것이 포인트이다
1. 모든 직선 쌍에 대해 반복
<ul>
<li>모든 직선 쌍에대해 반복을 이중 반복문으로 구현한다.</li>
</ul>
<pre><code>for(int i =0; i &lt; line.length; i++) {
 for (int j =i +1; j &lt; line.length; j++){
 //line[i], line[j]를 이용하여 1-A, 1-B 수행
 }
 }</code></pre>
1-A. 교점 좌표 구하기
<ul>
<li>두 직선의 교점을 구해야하는데 별도의 메서드로 분리하여 구현한다.</li>
</ul>
<pre><code>//교점 구해서 반환하기
private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2){

 return null;
}</code></pre>
<a href="https://www.google.com/search?q=%EA%B5%90%EC%A0%90+%EC%A2%8C%ED%91%9C+%EA%B5%AC%ED%95%98%EA%B8%B0&amp;rlz=1C5CHFA_enKR935KR935&amp;oq=%EA%B5%90%EC%A0%90+%EC%A2%8C%ED%91%9C+%EA%B5%AC%ED%95%98%EA%B8%B0&amp;gs_lcrp=EgZjaHJvbWUqBwgAEAAYgAQyBwgAEAAYgAQyBwgBEAAYgAQyCAgCEAAYBRgeMggIAxAAGAUYHjIICAQQABgFGB4yCAgFEAAYBRge0gEIMjE4NGoxajeoAgCwAgA&amp;sourceid=chrome&amp;ie=UTF-8#fpstate=ive&amp;vld=cid:43010b73,vid:_TyxFtRdJtw,st:0">교점 좌표 구하기 참고(연립2차방정식 풀이)</a>
<img src="https://velog.velcdn.com/images/psj0810/post/0114436d-b84b-4ee6-9e94-88ab312609cd/image.png"> 
위 식을 이용한 교점을 구하는 방식은 아래에 참고사항으로 나와있다. 
<img src="https://velog.velcdn.com/images/psj0810/post/858f0ad1-7b50-40fe-b741-39bfcfb23a2d/image.png">
<pre><code>
private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2){
		//교점 구하기
 double x = (double) (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
 double y = (double) (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
 
 // 정수일때만 반환
 if(x % 1 != 0 || y % 1 != 0) return null;
 
 return new Point((long) x, (long) y);
}</code></pre>
1-B. 정수 좌표만 저장
<pre><code>List&lt;Point&gt; points new ArrayList&lt;&gt;();
for(int i = 0; i &lt; line.length; i++) {
	for (int j = i +1; j &lt; line.length; j++) {
 	 Point intersection = intersection(line[i][0],line[i][1],line[i][2],line[j][0],line[j][1],line[j][2])
 
 if(intersection != null) {
 	points.add(intersection);
 }
 
 }
}</code></pre>
2. 저장된 정수들에 대해 x,y 좌표의 최댓값, 최솟값 구하기
<ul>
<li>우리의 목표는 별을 표시할 2차원 배열을 정확히 별들만 표시할 수 있을 정도로 작게 잡아야한다.</li>
<li>이를 위해 각 좌표의 최댓값과 최솟값을 구해야 한다.</li>
</ul>
<pre><code>//가장 작은 좌표 찾기
private Point getMinimumPoint(Lint&lt;Point&gt; points) {
	//비교할 값을 먼저 만들어둠
	long x = Long.MAX_VALUE;
 long y = Long.MAX_VALUE;
 
 for(Point p : points){
 	if(p.x &lt; x) x = p.x;
 if(p.y &lt; y) y = p.y;
 }
 
 // 가장 작은 좌표를 가진 포인트 반환
 return new Point(x,y);
}</code></pre>
<pre><code>//가장 큰 좌표 찾기
private Point getMaximumPoint(Lint&lt;Point&gt; points) {
	//비교할 값을 먼저 만들어둠
	long x = Long.MIN_VALUE;
 long y = Long.MIN_VALUE;
 
 for(Point p : points){
 	if(p.x&gt;x) x = p.x; 
 if(p.y&gt;y) y = p.y; 
 }
	
 // 가장 큰 좌표를 가진 포인트 반환
 return new Point(x,y);
}</code></pre>
3. 구한 최댓값, 최솟값을 이용하여 2차원 배열의 크기 결정
<ul>
<li>배열의 크기를 구해야 하므로 minimum과 maximum을 사용하여 구한 값에 1을 더해야한다</li>
</ul>
<blockquote>
✅ 왜 +1을 하는 걸까?
배열은 0부터 시작하는 인덱스를 사용하기 때문에, 시작점과 끝점을 모두 포함하려면 범위 차이에 <code>+1</code>을 해줘야 함.
예: 
👉 minimum = (2, 3) 
👉 maximum = (5, 8)
2~5까지는 4개의 값 (2, 3, 4, 5)
3~8까지는 6개의 값 (3, 4, 5, 6, 7, 8)
</blockquote>
<pre><code>Point minimum = getMinimumPoint(points);
Point maximum = getMaximumPoint(points);

int width = (int) (maximum.x - minimum.x + 1);
int height = (int) (maximum.y - minimum.y + 1);

char[][] arr = new char[height][width]; //배열 기준은 행 열
for (char[] row : arr) {
	Arrays.fill(row, '.');
}</code></pre>
<ul>
<li>최소값과 최대값을 이용하여 width와 height을 구한다.</li>
<li>width와 height을 이용하여 2차원 배열을 만든다.</li>
<li>한 행씩 가져와서 그 행의 내부 배열값을 모두 <code>.</code>으로 채운다.</li>
<li>문자를 넣어야하므로 자료형은 <code>char</code> 로 한다.</li>
<li><code>Arrays.fill(row, '.')</code> 는 <code>row</code> 배열의 모든값을 <code>.</code>으로 채운다는 것이다.</li>
</ul>
4. 2차원 배열에 별 표시
<ul>
<li>별을 찍는다.</li>
<li>별을 찍을 위치는 <code>1-B</code> 에서 <code>points</code> 변수에 저장했으니 이를 순회하며 별을 찍어준다.</li>
</ul>
<pre><code>for(Point p : points) {
	int x = (int) (p.x - minimum.x);
 int y = (int) (maximum.y - p.y);
 arr[y][x] = '*'; // 좌표에서는 x,y순이지만 배열에서는 행 열 수준이라 [y][x]로 바꿔줌
}</code></pre>
<img src="https://velog.velcdn.com/images/psj0810/post/6af4bd46-b1e9-4419-b08b-08e488e8376c/image.png">
4-1. 이렇게하는 이유
<blockquote>
<pre><code>int x = (int) (p.x - minimum.x);</code></pre>
먼저 points 들의 모든 값들은 교점들이고 
minimum.x는 그 교점들중 최소값이다.
우리는 교점이 있는 최소한의 배열만 만들것이다.
points들 중 최소값은 minimum.x 와 값이 일치할것이고 
points 중 p.x - mimun.x를 하면 0 으로 초기화 될것이다.
그럼 x값을 배열의 0부터 시작하게 넣을 수있는것이다.
</blockquote>
4-2. 이렇게하는 이유
<blockquote>
<pre><code>int y = (int) (maximum.y - p.y);</code></pre>
<img src="https://velog.velcdn.com/images/psj0810/post/b4423944-f69f-4870-88dd-6fb630df5a87/image.png">
<img src="https://velog.velcdn.com/images/psj0810/post/21907077-7f55-487f-9807-dc72743252cd/image.png">
maximum.y는 points중 가장 큰값이고 maximum.y에서 points 에서 가져오는 p.y를 빼줘야 배열의 순서대로 y값이 들어간다.
</blockquote>
5. 문자열 배열로 변환 후 반환
<pre><code>//char[][] arr 에서 만든 행 개수 -&gt; arr.length
String[] result = new String[arr.length]; 

for (int i =0; i &lt; result.length; i++) {
	result[i] = new String(arr[i]);
}
return result;</code></pre>
<ul>
<li>
<code>arr[i]</code>는 <code>char[]</code> → 한 행의 문자 배열 (예: <code>['.', '*', '.']</code>)
</li>
<li>
<code>new String(arr[i])</code>은 그 문자 배열을 문자열로 변환 (예: <code>".*."</code>)
</li>
<li>
그걸 <code>result[i]</code>에 저장
</li>
</ul></div></div>

psj.log

문제 풀이 흐름
모든 직선 쌍에 대해 반복
 A. 교점 좌표 구하기
 B. 정수 좌표만 저장
저장된 정수들에 대해 x,y 좌표의 최대값, 최소값구하기
구한 최대값, 최솟값을 이용하여 2차원 배열의 크기 결정
2차원 배열에 별 표시
문자열 배열로 변환 후 반환
좌표를 표현해야하니 좌표를 나타내는 클래스를 만든다
class Point{
 long x;
 long y;
 Point(long x, long y){
 this.x = x;
 this.y = y;
 }
}
무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
위 제한사항에서 직선 하나는 직선 하나와만 교차한다는 것이 포인트이다
1. 모든 직선 쌍에 대해 반복
모든 직선 쌍에대해 반복을 이중 반복문으로 구현한다.
for(int i =0; i < line.length; i++) {
 for (int j =i +1; j < line.length; j++){
 //line[i], line[j]를 이용하여 1-A, 1-B 수행
 }
 }
1-A. 교점 좌표 구하기
두 직선의 교점을 구해야하는데 별도의 메서드로 분리하여 구현한다.
//교점 구해서 반환하기
private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2){
 return null;
}
교점 좌표 구하기 참고(연립2차방정식 풀이)
위 식을 이용한 교점을 구하는 방식은 아래에 참고사항으로 나와있다.
private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2){
 //교점 구하기
 double x = (double) (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
 double y = (double) (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
 // 정수일때만 반환
 if(x % 1 != 0 || y % 1 != 0) return null;
 return new Point((long) x, (long) y);
}
1-B. 정수 좌표만 저장
List<Point> points new ArrayList<>();
for(int i = 0; i < line.length; i++) {
 for (int j = i +1; j < line.length; j++) {
 Point intersection = intersection(line[i][0],line[i][1],line[i][2],line[j][0],line[j][1],line[j][2])
 if(intersection != null) {
 points.add(intersection);
 }
 }
}
2. 저장된 정수들에 대해 x,y 좌표의 최댓값, 최솟값 구하기
우리의 목표는 별을 표시할 2차원 배열을 정확히 별들만 표시할 수 있을 정도로 작게 잡아야한다.
이를 위해 각 좌표의 최댓값과 최솟값을 구해야 한다.
//가장 작은 좌표 찾기
private Point getMinimumPoint(Lint<Point> points) {
 //비교할 값을 먼저 만들어둠
 long x = Long.MAX_VALUE;
 long y = Long.MAX_VALUE;
 for(Point p : points){
 if(p.x < x) x = p.x;
 if(p.y < y) y = p.y;
 }
 // 가장 작은 좌표를 가진 포인트 반환
 return new Point(x,y);
}
//가장 큰 좌표 찾기
private Point getMaximumPoint(Lint<Point> points) {
 //비교할 값을 먼저 만들어둠
 long x = Long.MIN_VALUE;
 long y = Long.MIN_VALUE;
 for(Point p : points){
 if(p.x>x) x = p.x; 
 if(p.y>y) y = p.y; 
 }
 // 가장 큰 좌표를 가진 포인트 반환
 return new Point(x,y);
}
3. 구한 최댓값, 최솟값을 이용하여 2차원 배열의 크기 결정
배열의 크기를 구해야 하므로 minimum과 maximum을 사용하여 구한 값에 1을 더해야한다
✅ 왜 +1을 하는 걸까?
배열은 0부터 시작하는 인덱스를 사용하기 때문에, 시작점과 끝점을 모두 포함하려면 범위 차이에 +1을 해줘야 함.
예:
👉 minimum = (2, 3)
👉 maximum = (5, 8)
2~5까지는 4개의 값 (2, 3, 4, 5)
3~8까지는 6개의 값 (3, 4, 5, 6, 7, 8)
Point minimum = getMinimumPoint(points);
Point maximum = getMaximumPoint(points);
int width = (int) (maximum.x - minimum.x + 1);
int height = (int) (maximum.y - minimum.y + 1);
char[][] arr = new char[height][width]; //배열 기준은 행 열
for (char[] row : arr) {
 Arrays.fill(row, '.');
}
최소값과 최대값을 이용하여 width와 height을 구한다.
width와 height을 이용하여 2차원 배열을 만든다.
한 행씩 가져와서 그 행의 내부 배열값을 모두 .으로 채운다.
문자를 넣어야하므로 자료형은 char 로 한다.
Arrays.fill(row, '.') 는 row 배열의 모든값을 .으로 채운다는 것이다.
4. 2차원 배열에 별 표시
별을 찍는다.
별을 찍을 위치는 1-B 에서 points 변수에 저장했으니 이를 순회하며 별을 찍어준다.
for(Point p : points) {
 int x = (int) (p.x - minimum.x);
 int y = (int) (maximum.y - p.y);
 arr[y][x] = '*'; // 좌표에서는 x,y순이지만 배열에서는 행 열 수준이라 [y][x]로 바꿔줌
}
4-1. 이렇게하는 이유
int x = (int) (p.x - minimum.x);
먼저 points 들의 모든 값들은 교점들이고
minimum.x는 그 교점들중 최소값이다.
우리는 교점이 있는 최소한의 배열만 만들것이다.
points들 중 최소값은 minimum.x 와 값이 일치할것이고 
points 중 p.x - mimun.x를 하면 0 으로 초기화 될것이다.
그럼 x값을 배열의 0부터 시작하게 넣을 수있는것이다.
4-2. 이렇게하는 이유
int y = (int) (maximum.y - p.y);
maximum.y는 points중 가장 큰값이고 maximum.y에서 points 에서 가져오는 p.y를 빼줘야 배열의 순서대로 y값이 들어간다.
5. 문자열 배열로 변환 후 반환
//char[][] arr 에서 만든 행 개수 -> arr.length
String[] result = new String[arr.length]; 
for (int i =0; i < result.length; i++) {
 result[i] = new String(arr[i]);
}
return result;
arr[i]는 char[] → 한 행의 문자 배열 (예: ['.', '*', '.'])
new String(arr[i])은 그 문자 배열을 문자열로 변환 (예: ".*.")
그걸 result[i]에 저장

교점에 별 만들기

댓글