투 포인터의 이동 기준: 양끝 비교와 정렬 배열 병합

투 포인터에서는 두 위치를 움직일 기준을 어떻게 정하나요?

투 포인터는 두 위치를 따로 움직이며 이미 확인한 범위를 다시 보지 않는 방법입니다. 어느 포인터를 움직여도 되는 이유를 먼저 정해야 합니다.

Level은 소문자로 맞춘 뒤 양끝 l ↔ l, 다음 e ↔ e를 비교하면 회문임을 알 수 있습니다.

적용 조건·범위: 영문자만 남겨 회문을 판단하는 문제라면 필터링과 대소문자 통일을 먼저 적용합니다. 숫자를 남겨도 되는지는 문제 조건으로 결정합니다. 빈 문자열과 한 글자는 위 함수에서 true입니다.

본문 근거: C++ 표준 초안 — merge

이 글에서 할 일: 양끝 비교와 정렬 배열 병합에서 포인터 이동 이유를 설명합니다. 선수 지식: 배열 인덱스·반복문.

양끝 비교는 확인한 쌍을 제외합니다

아래 JavaScript 예제는 문자열의 양끝을 비교하며 회문인지 확인합니다. 코드 아래의 결과를 보면서 두 위치가 언제 안쪽으로 이동하고 비교가 언제 끝나는지 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function isPalindrome(text) {
  const s = text.toLowerCase(); // 이 예제의 입력은 ASCII 영문자
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

console.log(isPalindrome('Level'));
console.log(isPalindrome('Lever'));

실행 결과

true
false

반복문에 들어올 때 left 바깥쪽과 right 바깥쪽의 모든 쌍은 이미 같습니다. 현재 쌍도 같다면 두 위치를 동시에 안쪽으로 옮길 수 있습니다. 하나라도 다르면 즉시 실패입니다. 두 포인터가 만나거나 지나치면 비교할 쌍이 남지 않습니다.

영문자만 남겨 회문을 판단하는 문제라면 필터링과 대소문자 통일을 먼저 적용합니다. 숫자를 남겨도 되는지는 문제 조건으로 결정합니다. 빈 문자열과 한 글자는 위 함수에서 true입니다.

node --version

node palindrome.js

정렬 배열에서는 작은 쪽만 이동합니다

아래 JavaScript 예제는 정렬된 두 배열에서 현재 값을 비교해 작은 값부터 하나씩 모읍니다. 코드 아래의 결과와 표를 보면서 어느 배열의 위치가 이동하는지 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function mergeSorted(a, b) {
  let i = 0;
  let j = 0;
  const result = [];
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  while (i < a.length) result.push(a[i++]);
  while (j < b.length) result.push(b[j++]);
  return result;
}

console.log(JSON.stringify(mergeSorted([1, 4, 4], [2, 4])));

실행 결과

[1,2,4,4,4]

각 배열의 현재 값은 그 배열에 남은 값 중 최솟값입니다. 둘 중 작은 값을 결과 뒤에 넣어도 정렬 순서가 유지됩니다. 같은 값이면 왼쪽부터 넣는 규칙을 택했으며, 두 배열의 중복값은 모두 보존합니다. 한쪽이 끝나면 다른 쪽의 꼬리도 반드시 붙입니다.

node --version

node merge.js

교집합에서는 같을 때 양쪽을 이동합니다

교집합을 찾을 때 a[i] < b[j]라면 a의 현재 값은 b의 남은 값과 같을 수 없습니다. i만 증가합니다. 반대라면 j만 증가하고, 같으면 값을 기록한 뒤 둘 다 증가합니다.

중복 정책은 별도입니다. [1,1,2]와 [1,1,3]에서 같은 값을 매번 기록하면 [1,1]이라는 다중집합 교집합입니다. 값 하나씩만 필요한 집합 교집합이라면 같은 값의 구간을 건너뛰거나 마지막 출력값과 중복되는지 확인합니다.

두 배열 길이가 N, M이면 병합과 교집합 순회는 O(N+M) 시간입니다. 병합 결과는 O(N+M) 공간을 씁니다. 정렬되지 않았다면 비교 정렬 비용 O(N log N + M log M)을 별도로 고려합니다. 회문 비교는 O(N) 시간이며, 위 코드는 소문자 문자열을 만들어 O(N) 공간을 사용합니다.

직접 확인하고 문제에 적용하기

병합 함수에 빈 배열과 [2,2]를 넣으면 무엇이 나와야 할까요? 같은 값일 때 두 포인터를 모두 움직이면 병합 결과가 어떻게 달라질까요?

• 회문 문자열 풀이 — 양끝 비교 적용
• 두 정렬 배열 합치기 풀이
• 배열의 인덱스와 연산 비용

참고 자료

자료 확인일: 2026년 10월 19일.

• C++ 표준 초안 — merge — 정렬된 두 입력의 병합과 선형 비교 수.