💬 문제
xy 좌표 평면에 놓여있는 풍선들
풍선 마다 차지하고 있는 x 구간이 담긴 배열 points
특정 x 좌표에서 화살을 쏘면 수직 방향으로 쭉 지나감
모든 풍선을 터뜨릴 수 있는 최소 화살 개수 반환
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
✍️ 나의 풀이
/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function(points) {
points.sort((a, b) => {
return a[0] - b[0];
});
let cnt = 0;
let arr = [];
for (let i = 1; i < points.length; i++) {
if (!arr.length)
arr = points[i - 1];
if (arr[1] >= points[i][0]) {
arr[0] = Math.max(arr[0], points[i][0]);
arr[1] = Math.min(arr[1], points[i][1]);
} else {
arr = [];
cnt++;
}
}
return cnt + 1;
};가장 먼저 points 배열을 구간 시작점 기준으로 정렬
두번째 인덱스부터 순회하면서 앞 구간과 비교
현재 구간이 앞 구간과 합쳐질 수 있다면
두 구간의 시작점 중 큰 값이 새 구간의 시작점,
종료점 중 작은 값이 새 구간의 종료점이 됨
(= 두 구간이 겹치는 부분을 만드는 것)
합쳐진 새 구간이 존재한다면 다음에는 새 구간과 비교
더 이상 합쳐질 수 없다면 겹쳐져 있지 않다는 것이므로
새 구간은 초기화 시키고 화살 갯수 하나 증가
마지막 구간에 대해서 카운트하지 못했으므로 총 갯수에 +1하여 반환
📌 결과
Accepted
Runtime 199ms (Beats 86.89%)
Memory 73.03MB (Beats 49.23%)
📚 러닝 포인트
문제가 복잡하게 표현되어 있어서 그냥 구간 병합 문제랑 똑같은거 아닌가? 하고 돌려봤다가 결과를 보고 어떻게 동작하는 건지 깨달았다. 직접 테스트 케이스를 적어보면서 생각하니까 금새 겹치는 부분을 만들어가면 되겠다는 것을 알 수 있었다. 다만 이전까지 겹치는 부분을 담은 배열이 있을 때는 해당 배열과 비교하고, 아니면 앞 인덱스 구간과 비교해야 하는데 이걸 어떻게 if문으로 나눌까 고민을 조금 했다. 뭔가 코드가 깔끔해지지 않는 것 같아서 이 또한 조건을 나눠서 적어봤는데 무엇과 비교할지만 다르고, 그 이후의 동작은 모두 똑같길래 중복을 줄이기 위해서 if (!arr.length) arr = points[i - 1]로 해결했다. 별거 아닌 간단한 과정이지만 뭔가 뿌듯했다.
