난이도 : 실버 2
소요시간 : 1시간 10분
문제설명
문제 이해
- 태권도장은 2차원 좌표평면으로 표현되어 있다.
- 사범님은 (0,0) 에 앉아있다.
- i번 학생의 위치는 Xi, Yi 이다.
- 사범님은 보이는 학생들만 태권도를 열심히 한다고 판단한다고 가정했을때, 태권도를 열심히하는 사람이 몇명인지 구하라.("사범님에게 보인다는 것"이 정확히 무엇일까)
- 원점과 Xi, Yi를 이어 선분을 만들었을 때, 선분 위에 위치한 다른 학생이 아무도 없을 때사범님이 볼 수 있다.
예제 이해
아이디어
- 원점으로부터 특정 선까지의 거리가 같다는 것을 어떻게 확인할까?가 핵심인데 공교롭게도 원점이 주어지니 바로 기울기가 눈에 들어왔다.
- x증가량분의 y증가량이 기울기이므로 해당 기울기가 같은 점이 있다면 그 점중 원점이랑 더 가까운 점, 즉 (xi, yi)의 i가 원점과 더 가깝게 위치해 있으면 그 점만 보고 나머지 점은 보일 수 없다고 해석하였다.
- 따라서 해당 입력을 받고 그 입력을 기준으로 기울기를 계산하여 저장 후 , 기울기가 만약 같은 값이 있다면 거리를 비교하여 거리가 가까운 값만 채택하는 식으로 카운트를 증가시키는 것으로 생각해보았다.
문제풀이
1. 입력파싱
const N = Number(input[0]);
const arr = input.slice(1, N + 1).map(v => v.split(' ').map(Number));2. 기울기와 거리 계산
// 기울기와 거리 계산
const slope = arr.map(([x, y]) => ({
slope: Math.atan2(y, x),
distance: x * x + y * y,
x,
y
}));- Math.atan2(y, x)를 사용하여 각도를 계산.
- 거리의 제곱을 계산하여 distance로 저장
- 기울기(각도)를 기준으로 정렬하고, 같은 기울기인 경우 거리 기준으로 정렬합니다.
- 정렬된 리스트를 순회하며, 이전 기울기와 다른 경우에만 카운트를 증가시킵니다.
여기서 잠깐, Math.atan2가 뭘까?
필자는 처음에 Math.atan2에 대해 전혀 알지 못했다. 문서 에 (x,y)까지의 각도를 반환해준다고 나와있다.
왜 Math.atan2를 써야할까?
필자는 처음에 일반 기울기 구하는 공식인 y증가량/x증가량을 이용해 계산하려고 했다.
하지만 이렇게 해봤더니 실제로 아래와 같이 10점만 받는 것을 확인할 수 있다.
일단 y증가량/x증가량이 어떤 문제가 생기는지 알아보자.
먼저 기울기 계산에서 x가 0일경우 문제가 생긴다. 학생이 좌표의 x축 상에 있을 경우 기본적으로 x값이 0을 가지게 되는데 이 경우, y/x가 정의되지 않는 문제가 발생한다.
또한 , y/x기울기의 값이 동일한 경우 해당 좌표가 어느 사분면에 있는지 판별할 수 없다. 예를 들어 (1,-1)과 (-1,-1)의 경우 모두 기울기 1을 가지지만 (1,1)은 제 1사분면, (-1,-1)은 제 3사분면에 있다. 같은 기울기값이지만 서로 다른 반대방향으로 가리키는 경우 이를 같은 기울기로 처리하면 문제가 발생한다.
Math.atan2의 경우 이를 해결하는데 같은 기울기 값이더라도 이렇게 Angle값에 따라 모두 다르게 분류가 가능하다. 이는 사분면 정보와 기울기를 정확히 구할 수 있으므로 일반적으로 기울기를 구하는 방식보다 더 정교한 방법이라고 할 수 있다.
Point (1, 1): Slope = 1, Angle = 0.7853981633974483
Point (-1, -1): Slope = 1, Angle = -2.356194490192345
Point (-1, 1): Slope = -1, Angle = 2.356194490192345
Point (1, -1): Slope = -1, Angle = -0.78539816339744833. 기울기 기준으로 정렬, 기울기가 같으면 거리 기준으로 정렬
slope.sort((a, b) => {
if (a.angle === b.angle) {
return a.distance - b.distance;
}
return a.angle - b.angle;
});
4. 정렬된 리스틀 리용해 기울기가 같을 때 가장 가까운 학생만 남김
let visibleCount = 0;
let prevAngle = null;
for (const student of studentInfo) {
if (student.angle !== prevAngle) {
visibleCount++;
prevAngle = student.angle;
}
}정답코드
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filePath).toString().split('\n');
const N = Number(input[0]);
const arr = input.slice(1, N + 1).map(v => v.split(' ').map(Number));
// 기울기와 거리 계산
const slope = arr.map(([x, y]) => ({
angle: Math.atan2(y, x),
distance: x * x + y * y,
x,
y
}));
// 기울기 기준으로 정렬, 기울기가 같으면 거리 기준으로 정렬
slope.sort((a, b) => {
if (a.angle === b.angle) {
return a.distance - b.distance;
}
return a.angle - b.angle;
});
// 필터링하여 사범님에게 보이는 학생들만 남기기
let visibleCount = 0;
let prevAngle = null;
for (const student of slope) {
if (student.angle !== prevAngle) {
visibleCount++;
prevAngle = student.angle;
}
}
console.log(visibleCount);
I want to become a UX Developer