수달씨의 개발공간

LeetCode 167: Two Sum II - Input Array Is Sorted

📌 문제 설명

주어진 정렬된 배열에서 두 숫자의 합이 주어진 target과 일치하는 인덱스를 반환하는 문제입니다.
배열의 인덱스는 1부터 시작하고, 합이 일치하는 두 숫자의 인덱스를 1-based로 반환해야 합니다.

✅ 풀이 아이디어: Two Pointers 알고리즘

이 문제는 Two Pointers 기법을 사용하여 해결할 수 있습니다.

1. 배열이 정렬되어 있음을 이용해 left 포인터는 배열의 앞에서 시작하고, right 포인터는 배열의 끝에서 시작합니다.
2. 두 포인터의 합이 target보다 작으면 left를 증가시키고, 합이 크면 right를 감소시킵니다.
3. 두 포인터가 가리키는 값이 합이 target과 같다면 그 인덱스를 반환합니다.
4. 이러한 방식으로 한 번 순회하여 문제를 해결할 수 있습니다. 이때 **시간 복잡도는 O(n)**입니다.

✅ 구현 코드 (TypeScript)

export function twoSum(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const sum = numbers[left] + numbers[right];

    if (sum === target) {
      return [left + 1, right + 1]; // 1-based index
    }

    if (sum < target) {
      left++; // 합이 target보다 작으면 left 포인터를 증가
    } else {
      right--; // 합이 target보다 크면 right 포인터를 감소
    }
  }

  return [];
}

✅ 테스트 코드 (Jest)

describe("Medium 167: Two Sum II", () => {
  it("should return [1, 2] for [2, 7, 11, 15] and target 9", () => {
    expect(twoSum([2, 7, 11, 15], 9)).toEqual([1, 2]);
  });

  it("should return [1, 2] for [-1, 0] and target -1", () => {
    expect(twoSum([-1, 0], -1)).toEqual([1, 2]);
  });

  it("should return [1, 3] for [2, 3, 4] and target 6", () => {
    expect(twoSum([2, 3, 4], 6)).toEqual([1, 3]);
  });
});

✅ 시간 복잡도

• 시간 복잡도: O(n)
  • 배열을 한 번만 순회하므로, 시간 복잡도는 배열의 길이에 비례하여 선형입니다.
• 공간 복잡도: O(1)
  • 추가적인 공간을 사용하지 않으므로 공간 복잡도는 상수입니다.

✅ 마무리

이 문제를 풀면서 중간 난이도 문제도 이제는 한 번에 풀 수 있게 된 것 같다는 자신감이 생겼습니다.
Two Pointers 알고리즘을 통해 정렬된 배열에서 빠르게 답을 찾는 기법을 잘 활용한 문제였습니다. 이제는 이런 유형의 문제를 더 잘 풀 수 있을 것 같아요.

🔗 문제 링크: https://leetcode.com/problems/is-subsequence/

📌 문제 설명

두 문자열 s와 t가 주어졌을 때, 문자열 s가 t의 **부분 수열(subsequence)**인지 판별하는 문제입니다.

🔹 Subsequence란?

• 원래 문자열에서 일부 문자를 삭제하여 얻을 수 있는 문자열
• 문자의 상대적인 순서가 유지되어야 함
• 연속될 필요는 없음

예시:

• "abc" → "ahbgdc" 는 부분 수열 ✅
• "axc" → "ahbgdc" 는 부분 수열 ❌ (x가 순서상 없음)

✅ 해결 아이디어 - Two Pointers

문자열 s의 각 문자가 문자열 t 안에서 순서를 유지한 채 등장하는지만 확인하면 됩니다.

🔹 전략

• 두 포인터 i, j를 각각 t, s를 탐색하는 인덱스로 사용
• t[i] === s[j]면 j를 증가시켜 s의 다음 문자로 이동
• j === s.length에 도달하면 모든 문자가 매칭된 것이므로 true

✅ 구현 코드 (TypeScript)

export function isSubsequence(s: string, t: string): boolean {
  let j = 0;
  for (let i = 0; i < t.length && j < s.length; i++) {
    if (t[i] === s[j]) {
      j++;
    }
  }
  return j === s.length;
}

🧪 테스트 코드 (Jest)

describe("Easy 392: Is Subsequence", () => {
  it("returns true when s is a subsequence of t", () => {
    expect(isSubsequence("abc", "ahbgdc")).toBe(true);
  });

  it("returns false when s is not a subsequence of t", () => {
    expect(isSubsequence("axc", "ahbgdc")).toBe(false);
  });
});

📈 시간 및 공간 복잡도

항목 복잡도

✅ 마무리 정리

• 핵심은 s의 각 문자가 t 안에서 순서를 유지하며 존재하는지를 확인하는 것
• Two Pointers를 통해 한 번의 순회로 간단하게 해결 가능

🔗 문제 링크: https://leetcode.com/problems/valid-palindrome/

📌 문제 설명

주어진 문자열 s가 알파벳과 숫자만 고려하고, 대소문자 구분 없이 앞뒤가 같은 회문(palindrome)인지 판별하는 문제입니다.

🔹 조건 요약

• 영문자와 숫자만 유효 문자로 간주
• 대소문자 구분 없이 비교
• 회문: 앞에서 읽어도, 뒤에서 읽어도 같은 문자열

✅ 해결 아이디어 - Two Pointers

이 문제는 양쪽 끝에서 문자를 비교하며 회문 여부를 판단하는 투 포인터(Two Pointers) 알고리즘으로 풀 수 있습니다.

🔹 전략

• left, right 두 포인터를 사용해 문자열의 양쪽 끝에서 시작
• 알파벳/숫자가 아닌 문자는 건너뜀
• 영문자는 소문자로 통일 후 비교
• 두 문자가 다르면 false 반환, 끝까지 같으면 true

✅ 구현 코드 (TypeScript)

export function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  const makeLower = (char: string) => {
    if (char >= "A" && char <= "Z") {
      return String.fromCharCode(char.charCodeAt(0) + 32);
    } else if (char >= "a" && char <= "z") {
      return char;
    } else if (char >= "0" && char <= "9") {
      return char;
    } else {
      return "";
    }
  };

  while (left < right) {
    const l = makeLower(s[left]);
    const r = makeLower(s[right]);

    if (l === "") {
      left++;
      continue;
    }
    if (r === "") {
      right--;
      continue;
    }
    if (l !== r) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

🧪 테스트 코드 (Jest)

describe("LeetCode 125: Valid Palindrome", () => {
  it("simple palindrome", () => {
    expect(isPalindrome("A man, a plan, a canal: Panama")).toBe(true);
  });

  it("not a palindrome", () => {
    expect(isPalindrome("race a car")).toBe(false);
  });

  it("empty string", () => {
    expect(isPalindrome("")).toBe(true);
  });

  it("numbers and letters", () => {
    expect(isPalindrome("0P")).toBe(false);
  });
});

✅ 시간 및 공간 복잡도

항목 복잡도

✅ 마무리 정리

• 핵심은 알파벳과 숫자만 추려서 비교하는 것
• 앞뒤 포인터를 사용하면 한 번의 순회로 문제 해결 가능
• 문자열 전처리 없이도 바로 비교하며 진행하는 방식이 효율적

✅ 개념 정의

Two Pointers(투 포인터) 알고리즘은 두 개의 인덱스(포인터)를 이용해 배열이나 문자열을 효율적으로 탐색하는 알고리즘 기법입니다. 보통 O(N) 시간에 문제를 해결할 수 있어, 정렬된 데이터나 연속된 구간을 처리할 때 유용합니다.

✅ 언제 사용하는가?

상황 설명

✅ 패턴 1: 양쪽에서 좁혀오는 방식

🔹 구조

let left = 0;
let right = arr.length - 1;

while (left < right) {
  if (arr[left] + arr[right] === target) {
    return [left, right];
  } else if (arr[left] + arr[right] < target) {
    left++;
  } else {
    right--;
  }
}

🔹 사용 예시: 정렬된 배열에서 합이 target인 쌍 찾기

const arr = [1, 2, 3, 4, 6];
const target = 6;
// 출력: [1, 3] (2 + 4)

• 포인터를 왼쪽/오른쪽에서 이동하며 값을 비교
• 정렬된 배열일 때 효율적으로 동작함

✅ 패턴 2: 앞뒤 포인터로 구간 조절 (슬라이딩 윈도우)

🔹 구조

let left = 0;
let sum = 0;

for (let right = 0; right < arr.length; right++) {
  sum += arr[right];

  while (sum > target) {
    sum -= arr[left++];
  }

  if (sum === target) {
    console.log(`Found from ${left} to ${right}`);
  }
}

🔹 사용 예시: 부분 배열의 합이 target과 같은 구간 찾기

const arr = [1, 2, 3, 4, 5];
const target = 9;
// 출력: Found from 1 to 3 (2 + 3 + 4)

• left와 right로 구간을 유연하게 이동
• 누적합과 비교하며 구간의 길이 조절

✅ 장점 요약

항목 설명

✅ 마무리 정리

Two Pointers는 다양한 배열/문자열 문제에 활용 가능한 강력한 도구입니다. 특히 정렬된 배열이나 구간 탐색 문제에서 매우 유용하며, 슬라이딩 윈도우와 함께 쓰이기도 합니다.

복잡한 알고리즘보다도 간단한 반복문 조작으로 충분한 문제에서는 가장 먼저 고려해볼 전략입니다.

✅ 관련 문제 풀이

Easy

• 392. Is Substring?
• 125. Valid Palindrome

[LeetCode] Trapping Rain Water - 효율적인 해결 방법 (Two Pointers)

📌 문제 설명

LeetCode의 "Trapping Rain Water" 문제는 높이 배열(height[])이 주어질 때, 빗물이 고일 수 있는 총량을 계산하는 문제입니다.

• height[i]: 각 기둥의 높이
• 각 기둥의 너비는 1로 고정
• 빗물이 얼마나 고일 수 있는지 계산해야 함

📌 문제 해결 과정

✅ 잘못된 접근 (Brute Force, O(N²))

모든 인덱스에서 왼쪽 최대(leftMax)와 오른쪽 최대(rightMax) 를 찾아 빗물을 계산하는 방법이 떠오를 수 있습니다.

export function trap(height: number[]): number {
  let water = 0;

  for (let i = 1; i < height.length - 1; i++) {
    const leftMax = Math.max(...height.slice(0, i + 1));
    const rightMax = Math.max(...height.slice(i));

    water += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
  }

  return water;
}

🚨 문제점:

• Math.max(...arr)를 반복 호출해야 하므로 시간 복잡도 O(N²) 발생
• 배열이 길어질수록 매우 비효율적

📌 최적화된 해결 방법 (Two Pointers, O(N))

💡 핵심 아이디어: "양쪽에서 중앙으로 이동하며 작은 쪽을 기준으로 계산"

1. leftMax와 rightMax를 유지하면서 한 번의 순회로 해결
2. 작은 쪽(leftMax 또는 rightMax)을 기준으로 물을 계산
3. 양쪽 끝에서 중앙으로 이동하면서 빗물을 계산 (O(N))

✅ 작은 쪽을 기준으로 계산하는 이유:

• leftMax < rightMax라면 leftMax보다 높은 곳이 나오기 전까지 leftMax가 현재 위치에서 최대 물 저장 가능 높이
• 반대로 rightMax < leftMax라면 rightMax가 현재 위치에서 최대 물 저장 가능 높이

📌 최적화된 코드 (O(N))

export function trap(height: number[]): number {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }

  return water;
}

📌 예제 분석

입력:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

Step-by-step 실행 과정

left right leftMax rightMax water 설명

✅ 최종 결과: 6 (가둘 수 있는 물의 양)

📌 시간 복잡도 분석

접근법 시간 복잡도 설명

✅ Two Pointers 사용하면 O(N)으로 해결 가능! 🚀

📌 최종 정리

1. 각 위치에서 고일 수 있는 물의 양 = min(leftMax, rightMax) - height[i]
2. 모든 인덱스에서 leftMax와 rightMax를 찾는 것은 O(N²)로 비효율적
3. "양쪽 끝에서 중앙으로 이동하면서 작은 쪽을 기준으로 물을 계산"하면 O(N)으로 해결 가능
4. O(N) 탐욕법(Two Pointers)로 해결 가능!

💡 이제 비슷한 문제에서 "양쪽에서 중앙으로 이동하는 방식"을 떠올려 보세요! 🚀