인프런 커뮤니티 질문&답변
작성한 질문수
삽입정렬로 생각이 안나서 다르게 풀어봤습니다.
작성
·
134
0
삽입 정렬로 혼자 풀어보려고 했는데 도무지 생각이 안나서 버블정렬? 로 푼것 같습니다사실 버블정렬도 아닌것 같긴한데혹시 이렇게 풀면 너무 비효율적이거나 반례가 있을까요?
function solution(s, arr) {
let answer = new Array(s).fill(0);
answer[0] = arr[0];
for (let i = 1; i < arr.length; i++) {
if (answer.includes(arr[i])) {
for (let j = s - 1; j > 0; j--) {
if (answer[j] === arr[i]) {
[answer[j], answer[j - 1]] = [answer[j - 1], answer[j]];
}
}
} else {
answer.pop();
answer.unshift(arr[i]);
}
}
return answer;
}답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
코드에 대한 설명을 드리자면, 제공해주신 코드는 삽입 정렬이 아니라 캐시 메모리 구조에서의 LRU(Least Recently Used) 캐싱 전략을 구현한 것과 비슷해 보입니다. LRU 캐싱은 가장 최근에 사용되지 않은 항목을 교체하는 알고리즘입니다.
캐싱 로직을 배열로 구현하기 위해 includes 함수를 사용하여 배열에 현재 원소가 있는지 없는지 검사하고, 있는 경우 해당 원소를 찾는 순회 과정과 교체하는 과정을 거치고 있습니다. 원소가 배열에 없으면 가장 오래된 원소를 제거하고 새 원소를 배열의 맨 앞에 추가하고 있습니다.
이러한 방식은 캐싱 알고리즘 구현에 있어서 합당하지만, 정렬 알고리즘으로는 적합하지 않습니다. 효율적인 정렬을 위해 통상적인 삽입 정렬, 버블 정렬, 퀵 정렬 등의 방법이 주로 사용됩니다.
삽입 정렬은 각 번째 요소를 이미 정렬된 배열의 적절한 위치에 ‘삽입’하는 과정으로 이루어집니다. 제시해 주신 경우에 효율성 문제가 있을 수 있는데, includes를 사용하면 현재 값이 배열에 있는지 없는지 확인하기 위해 매번 배열 전체를 순회해야 하고, 배열의 요소를 교체할 때도 여러 연산이 필요하기 때문입니다.
정렬 알고리즘으로 작성하시려는 경우 각 정렬 방식의 기본적인 알고리즘이 어떻게 동작하는지를 먼저 숙지하신 후 구현을 시도해 보시는 것을 추천합니다.
참고URL:
https://www.inflearn.com/faq