-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
투포인터스 알고리즘으로 푸는 방법이 제가 이해한게 맞을까요?
24.01.14 16:50 작성 조회수 98
0
제가 이해한 걸로는 두개의 포인터 변수를 이용하여서 반복문을 하나를 가지고 문제를 푸는거라고 이해를 해서 아래와 같이 하나의 반복문으로 풀려고 노력했는데 해당 알고리즘이 제가 이해한 이론이 맞나요?
function solution(arr1, arr2) {
let answer = [];
let sorArr1 = arr1.sort((a, b) => a - b);
let sortArr2 = arr2.sort((a, b) => a - b);
let n = sorArr1.length;
let m = sortArr2.length;
let p1 = (p2 = 0);
while (p1 < n) {
if (sorArr1[p1] === sortArr2[p2]) {
answer.push(sorArr1[p1]);
}
p2++;
if (p2 === m - 1) {
p1++;
p2 = 0;
}
}
return answer;
}
console.log(solution([1, 3, 9, 5, 2], [3, 2, 5, 7, 8]));정답은 잘 나옵니다만... 핵심이 두개의 포인터 변수와 하나의 반복문만 사용한다 라고 기억 할려고 하는데 이게 맞을지...
답변을 작성해보세요.
0
인프런 AI 인턴
2024.01.16
안녕하세요, 인프런 AI 인턴입니다.
rhkdtjd_12님, 투 포인터스 알고리즘에 대한 이해가 꽤 잘 잡혀 있는 듯하네요.
예, 맞습니다. 투 포인터 알고리즘은 두 개의 포인트를 이용해서 주로 정렬된 배열에서 두 수의 합이나 차 같은 특정 조건을 만족하는 쌍을 효율적으로 찾는 데 사용됩니다. 보통 이 때 두 포인터는 각각 배열의 시작점과 끝점, 혹은 두 배열의 시작점에서 출발하는데, 포인터가 움직이는 조건에 따라 반복문 내에서 여러 상황을 처리할 수 있습니다.
제시해주신 코드를 보면 두 배열의 정렬된 원소들을 비교하며 공통된 값을 찾는 문제를 푸는 것으로 보입니다. 이런 종류의 문제 해결에 투 포인터 알고리즘이 적절히 사용된 경우라고 볼 수 있습니다. 다만, p2 포인터의 증가 조건과 p1 포인터의 증가 조건을 다시 살펴볼 필요가 있어요.
정확한 투 포인터 알고리즘은 두 배열의 각각의 포인터를 시작점에 놓고, 각 포인터가 가리키는 원소를 비교하며 두 포인터를 각각의 조건에 따라 이동시키면서 정답을 찾아나갑니다. 만약 sorArr1[p1]이 sortArr2[p2]보다 크다면 p2를 증가시켜야 하고, 반대의 경우에는 p1을 증가시켜야 하는 식으로 말이에요. 코드에서 p2 === m - 1 일 때만 p1을 증가시키고 있어서, 일반적인 투 포인터 알고리즘의 접근과는 조금 다릅니다.
아래는 수정된 코드 예시입니다.
function solution(arr1, arr2) {
let answer = [];
let p1 = 0, p2 = 0;
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
while (p1 < arr1.length && p2 < arr2.length) {
if (arr1[p1] === arr2[p2]) {
answer.push(arr1[p1]);
p1++;
p2++;
} else if (arr1[p1] < arr2[p2]) {
p1++;
} else {
p2++;
}
}
return answer;
}
위 코드처럼, 두 포인터가 각기 다른 배열의 시작점에서 출발해서 끝까지 움직이면서 조건에 맞춰서 두 포인터를 동시에 또는 별도로 이동시키는 방법이 일반적인 투 포인터 알고리즘 접근 방식입니다.
답변 1