인터뷰를 위한 Two Pointers HashMap Stack 패턴

코딩 인터뷰 알고리즘 필수 3가지 패턴

투 포인터(Two Pointers) 패턴은 두 개의 포인터를 사용해 데이터를 한 번에 스캔합니다. 회문(palindrome), 요소 쌍 찾기, 필터링 작업에서 시간 복잡도를 O(n²)에서 O(n)으로 줄여줍니다.

주요 변형 두 가지:

• 왼쪽-오른쪽(수렴): left는 인덱스 0에서 시작, right는 s.length - 1에서 시작. 대칭 확인을 위해 중앙으로 이동합니다.
• 느린-빠른(Slow-Fast): slow는 결과를 업데이트하고, fast는 중복 제거나 요소 이동을 위해 앞을 스캔합니다.

예시: 비알파벳 문자를 무시한 회문 확인.

const isPalindrome = (s) => {
  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("madam")); // true
console.log(isPalindrome("abc")); // false

해시맵: 빠른 조회와 그룹화

해시맵(객체 또는 Map)은 키-값 쌍을 저장해 O(1) 접근이 가능합니다. 빈도수 계산, 중복 확인, 아나그램, 캐싱에 딱 맞습니다.

알고리즘: 한 번 패스(build) 후 두 번째 패스(query). 중첩 루프를 완전히 생략합니다.

예시: 문자열에서 처음 등장하는 유일한 문자 찾기.

const firstUniqueChar = (s) => {
  const map = {};

  for (const char of s) {
    map[char] = (map[char] || 0) + 1;
  }

  for (const char of s) {
    if (map[char] === 1) {
      return char;
    }
  }

  return null;
};

console.log(firstUniqueChar("banana")); // 'b'
console.log(firstUniqueChar("aabbc")); // 'c'

스택: LIFO 구조 처리

스택은 Last In - First Out(LIFO)을 따릅니다. push/pop이 가능한 배열은 괄호 검증, 재귀 없는 스택, 백트래킹에 탁월합니다.

예시: 괄호 시퀀스 유효성 검증.

const isValidBrackets = (s) => {
  const stack = [];
  const map = {
    ')': '(',
    ']': '[',
    '}': '{' 
  };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (last !== map[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

console.log(isValidBrackets("{[()()]}")); // true
console.log(isValidBrackets("{[(])}")); // false

각 패턴 사용 시기

코딩 전에 이런 신호를 포착하세요:

투 포인터:

• 대칭이 있는 배열/문자열(회문).
• 요소 쌍 찾기.
• 정렬된 배열.
• 양 끝에서 비교.

해시맵:

• 빈도수나 유일성 계산.
• 아나그램, 그룹화.
• 요소 존재 확인.
• 빠른 조회가 필요한 비정렬 데이터.

스택:

• 괄호나 중첩 구조.
• LIFO 로직(마지막에 열린 게 먼저 닫힘).
• 백트래킹이나 상태 히스토리.

핵심 요약

• 투 포인터는 데이터 패스를 줄여 선형 구조에 최적.
• 해시맵은 O(1) 접근으로 중첩 루프를 두 패스로 대체.
• 스택은 재귀 없이 적절한 중첩 순서를 보장.
• 연습: 패턴별 10문제 풀고, 섞어 풀기.

이 패턴들은 LeetCode/Codewars 이지/미디엄 문제를 대부분 해결합니다. 꾸준히 사용하면 시니어급 인터뷰 직감을 키웁니다.

— Editorial Team