인프런 커뮤니티 질문&답변
작성한 질문수
섹션2 공통원소 구하기 정렬 없이 해봤는데 괜찮을까요??
작성
·
228
0
<html>
<body>
<script>
function solution(arr1, arr2) {
const answer = [];
const n = arr1.length;
const m = arr2.length;
let p1 = (p2 = 0);
while (p1 < n) {
if (arr1[p1] === arr2[p2]) {
answer.push(arr1[p1++]);
p2++;
} else {
p1++;
}
}
p1--;
while (p2 < m && p1 >= 0) {
if (arr2[p2] === arr1[p1]) {
answer.push(arr2[p2++]);
p1--;
} else {
p1--;
}
}
return answer.sort((a, b) => a - b);
}
const arr1 = [1, 3, 9, 5, 2];
const arr2 = [3, 2, 5, 7, 8];
console.log(solution(arr1, arr2));
</script>
</body>
</html>위와 같이 p1먼저 돌고
그 다음에 p2돌면서 p1을 뒤에서부터 찾았는데 이렇게 하는건 별로 일까요...?
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
shut up and squat님께서 질문하신 “섹션2 공통원소 구하기 정렬 없이 해봤는데 괜찮을까요??“에 대해 유사한 질문과 답변을 참고하시면 도움이 되실 것 같습니다.
공통원소 구하기 문제는 배열의 공통원소를 찾아내는 알고리즘 문제로써, 일반적으로 해시 테이블, 정렬 후 투 포인터 방식 등 다양한 방법으로 접근할 수 있습니다. 질문에서 사용하신 방법은 정렬 후 투 포인터 방식과 유사하지만, 두 배열에 대해 한 쪽을 끝까지 탐색하고 나머지 배열을 역순으로 탐색하는 독특한 방식을 사용하셨습니다.
이와 비슷한 접근 방식에 관하여 김태원 강사님께서 다음과 같이 조언해 주셨습니다:
자바스크립트의
includes()함수의 시간 복잡도가 O(n)인 것처럼,indexOf()또한 O(n)의 시간 복잡도를 가지며,shift()를 사용할 경우 각 요소들을 한 칸씩 이동해야 하므로 시간 복잡도가 O(n)입니다.
이는 고려하신 방법이 효율적인지 여부를 평가하는 데 도움이 됩니다.
또한 여기서 중요한 점은, 두 배열을 정렬하는 것이 먼저 필요하고, 이후에 투 포인터 알고리즘을 사용하여 O(n + m)의 시간 복잡도를 달성하여 더 효율적인 해결이 가능하다는 것입니다. 차례로 p1과 p2를 조작하는 방법은 불필요하게 다시 한 배열을 완전히 검사하는 것과 같아 시간 복잡도 측면에서 비효율적일 수 있다는 조언을 제공합니다.
특히 아래의 답변 링크에서 더 자세한 내용을 확인하실 수 있습니다:
- 이런식으로 p1 p2를 안써도 괜찮을까요 ? -
shift()메서드의 시간 복잡도에 대한 설명 및 효율성 측면에서의 조언이 이와 관련 있습니다.
- 어떻게 푸는 것이 더 옳은 방법인가요? - 포인터 사용과 관련하여 시간 복잡도의 중요성을 강조한 답변이 나와 있습니다.
질문하신 방식이 문제를 해결하기는 하겠지만, 여러가지 요소를 고려해 볼 때 보다 효율적인 방법을 사용하는 것이 코딩 테스트에서 더 좋은 점수를 받는 방법입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.