수달씨의 개발공간

📌 문제 설명

문자열 haystack에서 부분 문자열 needle이 처음으로 등장하는 인덱스를 찾아 반환하는 문제입니다.

🔹 문제 해석

주어진 두 문자열 needle과 haystack이 있을 때, haystack에서 needle이 처음으로 등장하는 인덱스를 반환하라. 만약 존재하지 않으면 -1을 반환하라.

🔹 예시

Input: haystack = "sadbutsad", needle = "sad"
Output: 0

Input: haystack = "leetcode", needle = "leeto"
Output: -1

🔹 단어 정리

단어 의미

✅ 풀이 아이디어

• 부분 문자열 needle의 길이 len만큼 haystack을 슬라이딩 윈도우 방식으로 잘라서 비교
• 일치하는 순간 인덱스를 반환하고, 없으면 -1 반환

🔸 예외 처리

• needle이 빈 문자열이면 0 반환하는 것이 일반적 (LeetCode 기준)

✅ TypeScript 코드

export function strStr(haystack: string, needle: string): number {
  const len = needle.length;

  for (let i = 0; i <= haystack.length - len; i++) {
    if (haystack.slice(i, i + len) === needle) {
      return i;
    }
  }

  return -1;
}

✅ 시간 및 공간 복잡도

항목 복잡도

• N: haystack의 길이
• M: needle의 길이
• 보통 대부분의 테스트 케이스에서 매우 빠르게 동작

✅ Jest 테스트 코드

describe("LeetCode 28: Find the Index of the First Occurrence in a String", () => {
  it("returns 0 when needle is at the start", () => {
    expect(strStr("sadbutsad", "sad")).toBe(0);
  });

  it("returns -1 when needle is not present", () => {
    expect(strStr("leetcode", "leeto")).toBe(-1);
  });

  it("returns index when needle appears in the middle", () => {
    expect(strStr("hello", "ll")).toBe(2);
  });

  it("returns 0 for empty needle", () => {
    expect(strStr("abc", "")).toBe(0);
  });
});

✅ 마무리 정리

• slice()로 부분 문자열 비교하며 탐색하는 간단한 슬라이딩 윈도우 방식
• 내장 함수 없이도 직접 구현 가능
• KMP 알고리즘을 배우면 성능을 더 향상시킬 수 있음

📌 문제 설명

문자열을 지그재그(Zigzag) 형태로 재배치하고, 각 행(row)을 위에서 아래로 읽은 결과를 반환하는 문제입니다.

🔹 문제 요약

• 문자열 s와 정수 numRows가 주어짐
• 문자열을 지그재그 형태로 numRows 만큼의 행에 작성
• 이후 행을 위에서 아래로 읽은 결과를 반환

🔹 예시

s = "PAYPALISHIRING", numRows = 3

P   A   H   N
 A P L S I I G
  Y   I   R

=> 결과: "PAHNAPLSIIGYIR"

✅ 풀이 아이디어

🔸 흐름 요약

• 각 행에 도달할 때마다 방향을 바꾸며 문자를 할당
• curRow: 현재 행 인덱스
• goingDown: 방향 (아래로 가고 있는지 여부)
• 각 행별 문자열을 따로 모아서 마지막에 합치면 정답

🔸 시각화 예시 (numRows = 4)

s = "PAYPALISHIRING"

P     I    N
 A   L S  I G
  Y A   H R
   P     I

결과: "PINALSIGYAHRPI"

✅ TypeScript 코드

export function convert(s: string, numRows: number): string {
  if (numRows === 1 || s.length <= numRows) {
    return s;
  }

  const rows: string[] = new Array(numRows).fill("");
  let curRow = 0;
  let goingDown = false;

  for (const char of s) {
    rows[curRow] += char;
    if (curRow === 0 || curRow === numRows - 1) {
      goingDown = !goingDown;
    }
    curRow += goingDown ? 1 : -1;
  }

  return rows.join("");
}

✅ 예외 처리

• numRows가 1이거나 문자열 길이보다 크면 그대로 반환 (지그재그 적용 불필요)

✅ 공간 최적화 아이디어

• rows는 string[] 대신 string[][] 형태로 구현하면 성능 개선 가능

const rows: string[][] = Array.from({ length: numRows }, () => []);

for (const char of s) {
  rows[curRow].push(char);
  if (curRow === 0 || curRow === numRows - 1) goingDown = !goingDown;
  curRow += goingDown ? 1 : -1;
}

return rows.map(row => row.join("")).join("");

✅ 문자열을 직접 연결하는 대신 문자 배열을 사용해 중간 문자열 생성을 줄임

📈 시간 및 공간 복잡도

항목 복잡도 설명

🧪 테스트 예시 (Jest)

describe("LeetCode 6: Zigzag Conversion", () => {
  it("returns correct zigzag conversion for 3 rows", () => {
    expect(convert("PAYPALISHIRING", 3)).toBe("PAHNAPLSIIGYIR");
  });

  it("returns correct zigzag conversion for 4 rows", () => {
    expect(convert("PAYPALISHIRING", 4)).toBe("PINALSIGYAHRPI");
  });

  it("returns input if numRows is 1", () => {
    expect(convert("ABCD", 1)).toBe("ABCD");
  });
});

✅ 마무리 정리

• 문자열을 지그재그로 나눈 후 행 단위로 이어붙이기만 하면 되는 단순한 문제
• 방향 제어(위/아래) 와 행 포인터(curRow) 를 잘 사용하면 쉽게 구현 가능
• 문자열 재조합 문제의 전형적인 예시로 활용도 높음

[LeetCode 14] Longest Common Prefix - 가장 긴 공통 접두사 구하기

📌 문제 설명

주어진 문자열 배열에서 가장 긴 공통 접두사를 찾아 반환하는 문제입니다.

🔹 문제 원문

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
You may assume that all strings consist of lowercase English letters only.

🔹 해석

• 문자열 배열에서 가장 긴 공통 접두사를 찾는 함수를 작성하라.
• 공통 접두사가 없다면 빈 문자열 ""을 반환한다.
• 모든 문자열은 소문자 알파벳으로만 구성된다.

🔹 단어 정리

단어 뜻

✅ 내가 작성한 코드

export function longestCommonPrefix(strs: string[]): string {
  const lens = strs.map((str) => str.length);
  const len = lens.reduce((acc, cur) => Math.min(acc, cur), Infinity);

  for (let i = 0; i <= len; i++) {
    if (i === len) {
      return strs[0].slice(0, i);
    }

    const char = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (strs[j][i] !== char) {
        return strs[0].slice(0, i);
      }
    }
  }

  return "";
}

✅ 풀이 요약

• 모든 문자열의 길이 중 가장 짧은 값을 기준으로 반복
• 인덱스를 하나씩 증가시키며 문자열 배열의 같은 위치 문자가 모두 같은지 비교
• 다를 경우 그 이전까지가 공통 접두사 → slice(0, i) 반환

✅ 테스트 코드 (Jest)

describe("Easy 14: Longest Common Prefix", () => {
  it("has common prefix", () => {
    expect(longestCommonPrefix(["flower", "flow", "flight"])).toEqual("fl");
  });

  it("has no common prefix", () => {
    expect(longestCommonPrefix(["dog", "racecar", "car"])).toEqual("");
  });

  it("has one string", () => {
    expect(longestCommonPrefix(["a"])).toEqual("a");
  });

  it("shorter string first", () => {
    expect(longestCommonPrefix(["ab", "a"])).toEqual("a");
  });
});

📈 시간 및 공간 복잡도

항목 복잡도

✅ 마무리 정리

• 문자열 하나하나 비교하는 기본적인 접근이지만, 매우 안정적
• 사전순 정렬보다 효율적일 수 있음 (불필요한 연산 제거)
• 배열 탐색 & 문자열 비교 문제에서 기본기 다지기 좋은 문제