-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
코드리뷰 부탁드립니다!
23.12.14 21:10 작성 조회수 72
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
아래와 같이 풀어도 될까요 ?
아래와 같은 경우에 시간복잡도는 어떻게 될까요 ...?
const solution = (k, arr) => {
let answer = Array.from({ length: k }, () => 0);
for (let i = 0; i < arr.length; i++) {
if (!answer.includes(arr[i])) {
answer.unshift(arr[i]);
answer.pop();
} else {
let tmp = answer.filter((v) => v !== arr[i]);
tmp.unshift(arr[i]);
answer = tmp;
}
}
return answer;
};
console.log(solution(5, [1, 2, 3, 2, 6, 2, 3, 5, 7]));
답변을 작성해보세요.
0
인프런 AI 인턴
2023.12.16
안녕하세요, 인프런 AI 인턴입니다.
helloJS님, 제시해주신 자바스크립트 코드에 대한 시간 복잡도에 관해 답변 드리겠습니다.
주어진 코드는 크게 두 부분의 연산을 수행합니다. 먼저 if문 내부에서 answer.includes(arr[i])를 통한 요소 포함 여부 확인, 그리고 else문 내부에서 answer.filter를 통한 배열 필터링입니다.
includes 메서드는 배열 내에 특정 요소가 포함되어 있는지 확인할 때 배열의 모든 요소를 최악의 경우 확인해야 하므로 O(n)의 시간 복잡도를 가집니다. 그리고 filter 메서드 또한 배열의 모든 요소를 확인해야 하므로 O(n)의 시간 복잡도를 가집니다.
배열 arr의 길이를 n이라고 가정했을 때, 주어진 코드의 반복문은 n번 실행됩니다. 따라서 최악의 경우에는 includes와 filter가 각 반복마다 실행되어, 전체 시간 복잡도는 O(n^2)이 될 수 있습니다.
단, 반복문 내부에서는 최대 k개의 요소만을 answer 배열 내에 유지하므로 k가 작다면 복잡도는 상대적으로 낮아질 수 있습니다. 그러나 k가 크거나 n에 비례하여 증가한다면 n^2에 가까운 복잡도를 보일 것입니다.
코드 최적화를 고려한다면 includes와 filter 대신 다른 방법을 사용하여 시간 복잡도를 개선할 수 있는 방안을 고려해봐야 할 것 같습니다. 예를 들어, 해시 테이블 등을 사용하여 요소 확인을 O(1)로 줄일 수 있는 방법을 찾아볼 수 있습니다.
답변 1