레벨 0문제라고 얕보면 큰 코 다침 파트2
레벨0문제라고 금방 풀거라고 생각했으나... 고민과 여러번의 시도끝에 풀어냈다. 우선 모든 좌표를 비교해야했는데, for문을 돌리면 마지막 좌표와 첫번째 좌표는 비교할 수 없게되어 빼먹는 부분이 생겼다. 그래서 배열을 재조합하여 마지막 요소를 첫번째 요소로 하여 for문을 돌림으로서 모든 좌표를 2개씩 비교할 수 있게 하였다. (처음엔 정렬을 하였는데, 어차피 2개씩 비교하기때문에 굳이 정렬을 할 필요가 없어서 삭제하였다.)
두 선분을 비교할때, 왼쪽 최대값과 오른쪽 최소값의 차를 통해서 중복되는 부분을 알아낼 수 있었다. 그런데 여기서 다시 중복되는 부분이 발생할 수 있다. 아래 모식도를 그려보았다.
세 선분간의 중복 거리는 전체 좌표 중에서 왼쪽 최대값과 오른쪽 최소값의 차를 통해서 구할 수 있다. 마치 3개의 집합에서 합집합을 구할때, 2개씩의 교집합과 3개 모두 교집합을 빼서 한번씩만 더해지도록 만드는 원리와 비슷하다. 나는 이런 식의 선분의 좌표간의 최대값/최소값 비교를 통해서 문제를 풀 수 있었다.
function solution(lines) {
let overlap = 0;
let maxL = Number.MIN_SAFE_INTEGER,
minR = Number.MAX_SAFE_INTEGER;
const arr = [...lines, lines[0]];
for (let i = 0; i < arr.length - 1; i++) {
const [l1, r1] = arr[i];
const [l2, r2] = arr[i + 1];
const l = Math.max(l1, l2);
const r = Math.min(r1, r2);
maxL = Math.max(l, maxL);
minR = Math.min(r, minR);
if (r - l > 0) overlap += r - l;
}
return overlap - (minR - maxL > 0 ? (minR - maxL) * 2 : 0);
}나처럼 주먹구구(?)식보다는 뭔가 수학적인 풀이 있지 않을까 하는 기대감으로 다른 사람 풀이를 살펴보았다. 사실 대부분의 풀이들이 다 제각각이였고, 최대/최소를 활용해서 조건에 따라 분기하는 풀이들이 많았다. 그런데 이런 요상한 풀이를 보고 말았다. 무슨 말인고 했더니...와!!👍🏻 사실 이걸 이해했어도 내가 과연 다음번에 이런 생각을 할 수 있을까?? 라는 생각이 들지만, 그럼에도 좋은 아이디어이기에 풀이를 해석해보고자한다.
function solution(lines) {
let line = new Array(200).fill(0);
lines.forEach(([a, b]) => {
for (; a < b; a++) line[a + 100]++;
});
return line.reduce((a, c) => (c > 1 ? a + 1 : a), 0);
}new Array(200)라인의 요소는 -100 ~ 100 사이의 좌표이다. 그렇기때문에 저 배열 어딘가에 찍힐 수 있다.forEach는 a와 b사이를 순회하면 그 좌표에 해당하는 점들을 만들어놓은 line이란 배열 안에 1씩 더해준다.- 결국 line 배열 안에는 lines에 해당하는 모든 좌표가 있을 것이다. 중복되는 것들을 2 혹은 3의 카운팅이 될 것이다. 그래서 2이상인 점들만 다시 카운팅을 해주면 그게 바로 2번이상 중복된 길이가 된다.