시간 초과 해결
function solution(elements) {
const result = [];
const totalLength = elements.length;
for (let i = 1; i <= totalLength; i++) {
let left = 0;
let right = -1;
let total = 0;
while (left < totalLength) {
const diff = right - left + 1;
if (diff < i) {
right++;
total += elements[right % totalLength];
} else if (diff > i) {
total -= elements[left % totalLength];
left++;
} else {
if (!result.includes(total)) result.push(total);
right++;
total += elements[right % totalLength];
}
}
}
return result.length;
}위 코드는 윈도우 슬라이딩 이라는 알고리즘의 개념을 이용해서 구현해보려고 노력했다. 윈도우 슬라이딩 기법은 큰 배열에서 같은 일정한 길이(n)의 부분 배열이 위에서 한칸 한칸 움직일 때마다 변화하는 것을 구현하는 방법을 말한다. 마치 윈도우(부분 배열)가 슬라이딩 하는 것 같다고 해서 붙여진 이름이라고 한다. 그리고 이 개념을 사용하는 이유는 이중for문을 돌아야하는 것을 for문 한방에 풀 수 있도록 도와주기 때문이기도하다. (좀 더 효율성을 높여준다)
여기서는 결과적으로 이중for문으로 구현이 될 수 밖에 없는 조건이긴했다. 이 문제에서는 일정한 길이의 부분 배열이 n가지가 존재하기 때문이다. 그 말은 슬라이딩 윈도운 알고리즘을 n번 순회해야한다는 말이긴하다. 어쨌든 최대한 내가 이해한 슬라이딩 알고리즘을 통해서 구현해 보았다. 하지만 위 코드를 제출하니 1 ~ 3번 테스트 케이스를 제외한 모두 시간초과가 나왔다. 어디서 시간을 줄일 수 있을까?
여러 가지 질문을 참고해본 결과, 눈에 띄는 차이점은 중복제거를 위해서 Set 자료 구조를 이용했다. 그래서 나도 배열을 이용해서 중복을 체크하는 코드를 Set을 이용해 바꿔보았다.(몇줄만 변경됨!! 😇) 그랬더니 모든 테스트 케이스에서 통과하는 기적(?)을 발견하였다.
음... 우선 배운점은, 중복제거를 위해서 이제부터 Set을 사용하도록 하자. 그게 배열을 통해서 하는 것보다 효율이 더 좋다는 것을 이번에 경험적으로 배웠다.
function solution(elements) {
const result = new Set(); // ✅
const totalLength = elements.length;
for (let i = 1; i <= totalLength; i++) {
let left = 0;
let right = -1;
let total = 0;
while (left < totalLength) {
const diff = right - left + 1;
if (diff < i) {
right++;
total += elements[right % totalLength];
} else if (diff > i) {
total -= elements[left % totalLength];
left++;
} else {
result.add(total); // ✅
right++;
total += elements[right % totalLength];
}
}
}
return result.size; // ✅
}체크박스 부분이 Set에 의해 달라진 부분!
Set을 사용하지 않으면, 왜 효율이 좋은 것일까?? 코드적으로 봤을때, for > while > includes 이런 식의 중첩 구조를 가지고 있다. 여기서 includes 역시 내부적으로 for문을 돌기 때문에 결국 3중for문이 되기 때문에 이러한 시간 초과 오류가 발생했을까? 그래서 직접 배열을 사용했을 때와 Set을 사용했을 때를 성능차이를 직접 비교해보았다. 그 결과 배열을 사용했을 때가 성능적으로 1.5배 더 빨랐다.
[10000000번 반복]
Set : 4619.427999973297
Array : 3113.791375041008
[100000000번 반복]
Set : 44483.480541944504
Array : 31154.608958005905
왜 Array가 더 빠른데, 시간초과가 왜 나왔을까? 뭔가가 다른점이 있을까? 이런 저런 생각을 하던 중에 테스트 케이스에 대한 다양성에 대해서 생각하게 되었다. 위의 효율성 테스트는 짧은 배열을 인자([7,9,1,1,4])로 주고 이를 10000000번 / 100000000번 반복한 것에 대한 결과값이였다. 그래서 이번엔 가장 최악을 가정한 테스트 케이스를 만들어보기로 했다.
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
제한 조건이 위와 같기 때문에, 1000 길이에 1 ~ 1000 까지의 랜덤한 숫자인 배열을 만들어서 테스트 케이스를 실행해 보았다. 그랬더니 결과가 와....
Set : 40.73562502861023
Array : 124316.87304198742
이렇게나 차이가 나다니... 이러한 결과를 통해서 보면 includes(+ push)의 성능이 배열의 크기가 커질수록 안좋아진다는 사실을 알게 되었다. 이러한 결과값을 좀 더 정확하게 알기 위해서 몇가지 아티클을 찾아보았다.
위 내용은 몇가지 빌트인 배열 메소드에 대한 성능을 배열 크기에 따라서 비교해 본 결과값이다. includes가 일정 배열 크기까지는 가장 빠르다가 어느 순간 성능이 떨어지는 것을 볼 수 있다. 즉 위에서 내가 테스트 해본 결과와 일치함을 확인할 수 있었다. 일정 수준의 배열의 크기를 넘어가기 시작하면 성능이 굉장히 떨어짐을 알 수 있었다.
관련 아티클
-
Should You Use .includes or .filter to Check if An Array Contains an Item?
-
이 아티클은 결국 Arrary.includes()는 O(n)의 복잡도를 가지고 Set.has()는 O(1)의 복잡도를 갖기 때문에 데이터가 많아질수록 성능측면에서 Set이 유리하다라는 것을 증명하는 아티클이다.
의도치 않게 코드에 대한 성능 측면에 대해서 따지게 되었다. 그러면서 이번에 배운 것들은 중복 제거 / 확인 등과 같은 기능을 구현할 때는 Set을 잘 이용하면 성능적으로 좋을 것이라는 사실을 충분히 😆 인식할 수 있는 시간이였다.
추가적으로 성능에 대해서 검색하다보니 자연스럽게 성능과 가독성에 대한 논의 글도 많이 보게 되었다. 성능과 가독성 무엇이 중요한 것일까 등등... 해당 아티클도 첨부해본다. 지속적으로 생각해보면서 나만의 기준을 갖고 프로그래밍을 해야할 주제라고 생각한다.