🌈 시작하며
후... 정확성은 진작에 맞췄는데, 의문의 퍼포먼스 저하로(...) 효율성에서 계속해서 통과하지 못한 부분에 부딪히고 말았네요.
그렇지만, 모든 문제를 해결하는 과정이 그렇듯, 빠르게 해결하는 것을 추구하기보다는, 어떤 것을 배웠는지를 초점으로 문제를 살펴보아야 하는 것 같습니다.
그럼 시작해볼까요!
🔍 본론
일단 이 문제를 보자마자 떠오른 것은 이분 탐색과 비슷한 parametric search를 사용해야겠다는 것이었어요.
이유는 높이가 10억이라면, 결과적으로 완전탐색으로 하기에는 무리가 있어보였기 때문이었어요.
그렇다면, 우리는 무엇을 기준으로 parametric search를 진행해야 할까요?
🚦 조건
parametric search를 한다는 것은 결국 어떤 특정 결정 조건을 하나 설정하고, 이를 만족하지 않는 것은 살펴보지 않습니다.
따라서 저는 어떤 것을 결정할 수 있는 기준이 되는지를 설정해주어야 했어요.
이때, 저는 그냥 어렵게 생각하지 않고 다음과 같이 설정해줬습니다.
"가장 비용이 낮은 층인가?"
결국 비용이 낮으면 최적의 해를 선택할 수 있겠죠. 이제 우리는 이를 판별할 수 있는 알고리즘을 만들어줘야 하겠군요.
✨ 해결 방법 설계
따라서 이를 고민한 결과, 다음과 같은 특이한 사항이 떠올랐어요.
- 만약 현재 층이 배열 값으로 존재하지 않는다면?
- 1층 자체를 추가/제거하는 비용이 고스란히 들어가게 됩니다. 효율적이지 못해요. - 현재 층이 배열 값으로 존재한다면
- 최소한 배열의 인덱스 하나만큼은 비용이 0으로 들겠죠?
따라서 저는 이를 이용해서 1차원 배열로 만든 다음, 층 값을 고유하게 저장한 배열로 따로 만들어줬답니다.
const solution = (land, P, Q) => {
let result;
const flattedLand = land.flat();
const floorSet = [...new Set(flattedLand)].sort((a, b) => a - b);
...
}그 다음에는 계속해서 반씩 서치하기 위해 다음과 같이 포인터를 설정해줬어요.
let start = 0;
let end = floorSet.length;
let mid = Math.floor((start + end) / 2);비용 계산 로직
정말 쓸데 없이 간단했는데, 여기서 2시간이 걸렸습니다.
저는 Array.reduce를 사용하여 누산했는데요. 이것이 가장 큰 실수였습니다.
알고 계셨나요? 생각보다 자바스크립트에서
Array.reduce의 누산에 대한 시간 복잡도는 매우 큽니다!
이전에는 다음과 같이 비용을 계산하는 로직을 짰어요. 이유는 매우 직관적이었기 때문이죠.
일단 우리의 Kent 아저씨의 내용만 보더라도 최적화는 for을 쓰라고 하기도 하고, stackoverflow에서는 배열을 할당하는 데에 있어서 for문은 할당하지 않기에 효율적이라 하는군요!
const getCost = (mid) => {
if (mid === undefined || mid < 0 || mid > 1000000000) return Infinity;
return flattedLand.reduce(
(acc, cur) => {
const diff = mid - cur
return diff > 0
? acc + diff * P
: acc + (diff * -1) * Q
},
0
);
};실제로 이 식은 reduce로 직관적인 내용을 작성했다고 생각했지만, 효율성 4,5번을 통과하지 못했어요.
그러나 다음 식은 효율성을 매우 빠르게 통과해냈습니다.
const getCost = (mid) => {
if (mid === undefined) return Infinity;
let addBlockCnt = 0;
let removeBlockCnt = 0;
for (let i = 0; i < flattedLand.length; i += 1) {
const diff = mid - flattedLand[i];
if (diff > 0) {
addBlockCnt += diff;
} else {
removeBlockCnt += diff * -1;
}
}
return addBlockCnt * P + removeBlockCnt * Q;
};결정 조건 비교
그러면 우리는 어떨 때, 어떤 방식으로 업데이트해야 하는지를 살펴보아야겠죠? 🧐
저는 다음과 같은 생각을 했습니다.
현재 층은, 그 다음 층보다 작아야 무조건 해가 되지 않을까?
그도 그럴 것이, 다음 층 다음으로 배열에 포함된 층은 무조건 추가 비용이 다음 층 보다 추가비용이 더 클 수 밖에 없지요. 어떻게든 추가 비용이 더 생기니까요.
따라서 이를 이용해서 다음과 같이 비교 로직을 짰어요.
이분 탐색처럼, 만약 최적의 해면 업데이트 후 다시 mid를 아래쪽으로 설정해주고, 아니라면 위쪽으로 설정해주는 방식으로요!
while (start <= end) {
const midCost = getCost(floorSet[mid]);
const upperFloorCost = getCost(floorSet[mid + 1]);
if (midCost < upperFloorCost) {
result = midCost;
end = mid - 1;
} else {
start = mid + 1;
}
mid = Math.floor((start + end) / 2);
}이제 모든 로직을 다 짰습니다.
결과를 볼까요?
✅ 결과
빠르게 통과하는군요. 어썸합니다 🙆🏻
🖥 전체 코드
const solution = (land, P, Q) => {
let result;
const flattedLand = land.flat();
const floorSet = [...new Set(flattedLand)].sort((a, b) => a - b);
let start = 0;
let end = floorSet.length;
let mid = Math.floor((start + end) / 2);
const getCost = (mid) => {
if (mid === undefined) return Infinity;
let addBlockCnt = 0;
let removeBlockCnt = 0;
for (let i = 0; i < flattedLand.length; i += 1) {
const diff = mid - flattedLand[i];
if (diff > 0) {
addBlockCnt += diff;
} else {
removeBlockCnt += diff * -1;
}
}
return addBlockCnt * P + removeBlockCnt * Q
};
while (start <= end) {
const midCost = getCost(floorSet[mid]);
const upperFloorCost = getCost(floorSet[mid + 1]);
if (midCost < upperFloorCost) {
result = midCost;
end = mid - 1;
} else {
start = mid + 1;
}
mid = Math.floor((start + end) / 2);
}
return result;
};🔥 마치며
30분만에 정확도까지는 해결한 문제인데... 계산식 사태 + 정리까지 하고 나니까 거의 3시간이 족히 걸리는 말도 안되는 사태가 일어났군요.
그렇지만 오늘 이 문제를 풀면서 깨달았어요.
로직이 잘못되지 않더라도, 시간 복잡도에 영향을 미칠 수 있는 요인은 무궁무진하다는 것을 말이죠.
일단 문제 정확도가 풀렸는데 효율성에서 문제가 발생한다면, 앞으로는
- 내가 문제 시간복잡도에 효율적이지 않은 코드를 짰는지
- 다른 대안으로 다른 알고리즘을 사용할 수 있는지
로 순차적으로 봐야겠어요.
저는 1번을 고려하지 않고, 2번으로 가니... 결국 이런 실수를 저지른 것 같았거든요.
그래도, 덕분에 꽤나 좋은 인사이트를 얻어서 기분이 좋아요.
다들 저와 같은 실수를 하지 않기를 바라며, 즐거운 코딩하시길 바라요. 이상! 🌈
.jpg)