코딩테스트 문제를 풀다가 시간 초과 실패를 겪어본 적 누구나 있지 않은가? 일단 나는 굉장히 많다...ㅜ
그래서 조금이라도 시간 복잡도를 줄이는 것에 늘 생각하고 고민해보려 한다.
아예 접근 방식을 다르게 하는 것이 시간 복잡도 측면에서 가장 효율적이었던 경험이 많지만 같은 로직에서 간단한 조작 하나만으로 복잡도를 줄일 수 있는 방법이 있다.
바로 배열에 접근할 때 인덱스로 접근하는 것이다. 배열을 다룰 때 원본 배열을 그대로 둔 채 인덱스로만 값을 조종하는 방법은 상황에 따라 실행시간을 줄이는데 소소한 도움이 된다.
👁🗨 배열에 인덱스로 접근하는 예시
예시 1) 배열의 마지막 요소를 반복적 제거하는 과정
순서대로 pop 메서드를 사용하는 경우와 인덱스 값을 1씩 줄이는 방법을 사용하는 경우의 예시이다.
const array = [];
const size = 1000000;
for (let i = 0; i < size; i++) {
array.push(i);
}
while (array.length > 0) {
array.pop();
}const array = [];
const size = 1000000;
for (let i = 0; i < size; i++) {
array.push(i);
}
while (array.length > 0) {
array.length -= 1;
}pop 메서드를 사용하는 경우 - 배열의 길이가 줄어들 때마다 요소들을 한칸씩 앞으로 이동시켜야 하기 때문에 실행시간이 더 오래 걸린다.
인덱스 값을 1씩 줄이는 경우 - 배열의 길이를 바로 조절하여 요소들을 이동시키지 않으므로 실행시간이 더 짧게 걸린다.
예시 2) 배열에서 중복된 요소를 제거하는 과정
filter 메서드를 사용하는 경우와 인덱스를 이용하는 경우의 예시이다.
const array = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5];
const uniqueArray = array.filter((value, index, self) => self.indexOf(value) === index);const array = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5];
const uniqueArray = [];
for (let i = 0; i < array.length; i++) {
if (uniqueArray.indexOf(array[i]) === -1) {
uniqueArray.push(array[i]);
}
}filter 메서드를 사용하는 경우 - 각 요소마다 중복 여부를 확인하기 위해 배열 전체를 순회해야 하므로 실행 시간이 더 오래 걸린다.
인덱스를 사용하는 경우 - 각 요소의 중복 여부를 확인할 때 인덱스를 이용하여 확인하기 때문에 실행시간이 더 짧게 걸린다.
예시 3) 배열의 요소를 거꾸로 반전시키는 과정
reverse 메서드를 사용하는 경우와 인덱스를 이용하는 경우의 예시이다.
const array = [1, 2, 3, 4, 5];
const reversedArray = array.slice().reverse();const array = [1, 2, 3, 4, 5];
const reversedArray = [];
for (let i = array.length - 1; i >= 0; i--) {
reversedArray.push(array[i]);
}
reverse 메서드를 사용하는 경우는 간단하게 배열을 반전시킬 수 있으며 인덱스를 사용하는 경우는 배열의 각 요소를 역순으로 새로운 배열에 추가하여 반전 효과를 낼 수 있다.
사실 이 두 경우는 실행속도가 거의 비슷하게 나와서 성능상의 차이가 큰 것으로 보이지는 않는다..
🚨 주의할 점!! : 대용량 데이터에는 내장 메서드가 더 효율적일 가능성 ⏫
챗지피티에 물어보니 대용량 데이터 처리에는 내장 메서드를 사용하는 것이 성능적으로 더 우수한 방법이라고 한다. 이유는 다음과 같다
1) 최적화된 알고리즘
내장 메서드는 대개 언어 또는 런타임에 최적화 되어 있어 대용량 데이터에 대해서도 효율적으로 동작한다. 최선을 알고리즘을 선택하여 사용하기 때문에 처리속도가 더 빠를 수 있다.
2) 메모리 관리 및 최적화
메모리 관리와 최적화에 대한 다양한 고려사항을 내부적으로 다룬다. 이는 대용량 데이터를 효율적으로 처리하고 메모리를 효율적으로 활용하는데 도움이 된다.
3) 코드 간결성과 가독성
내장 메서드를 사용하는 것이 코드를 더 간결하고 가독성있게 작성할 수 있다. 이는 코드의 유지보수와 디버깅을 더 쉽게 만들어준다.
무조건 인덱스로 접근하는 것이 효율적이다! 라는 것이 아니라, 이렇게 하는 게 더 좋은 경우도 있다는 것을 알아주었으면 좋겠다. 선택할 수 있는 방법이 하나 더 늘어난 느낌으로..? 이제 상황에 따라 적합한 방법을 사용하는 법을 알아야겠다.
