수달씨의 개발공간

부분합이 특정 값을 넘는 가장 짧은 연속된 부분 배열의 길이를 구하는 문제입니다.
단순히 합만 구하는 것이 아니라, 길이까지 고려해야 하기에 효율적인 알고리즘이 필요합니다.
이 글에서는 Brute-force 접근 → 슬라이딩 윈도우 최적화 과정을 거쳐,
Dart로 완성도 높은 코드를 작성하고 이해하는 과정을 함께합니다.

📘 문제 설명

양의 정수 배열 nums와 목표값 target이 주어질 때,
합이 target 이상이 되는 연속된 부분 배열(subarray) 중에서
가장 짧은 길이를 반환하라.
없으면 0을 반환한다.

❌ Brute-force 접근 (비효율)

int minLength = nums.length + 1;

for (int i = 0; i < nums.length; i++) {
  int sum = 0;
  for (int j = i; j < nums.length; j++) {
    sum += nums[j];
    if (sum >= target) {
      minLength = min(minLength, j - i + 1);
      break;
    }
  }
}

• 시간복잡도: O(n²) → 큰 입력에서는 시간 초과 가능성 있음
• 매 i마다 전체 탐색 → 비효율적

✅ 최적화: 슬라이딩 윈도우

슬라이딩 윈도우는 합이 기준 이상일 때 길이를 최소화하는 문제에 딱 적합합니다.

💻 Dart 코드

class Solution {
  int minSubArrayLen(int target, List<int> nums) {
    int n = nums.length;
    int left = 0;
    int sum = 0;
    int minLength = n + 1;

    for (int right = 0; right < n; right++) {
      sum += nums[right];

      while (sum >= target) {
        minLength = minLength < (right - left + 1) ? minLength : (right - left + 1);
        sum -= nums[left];
        left++;
      }
    }

    return minLength == n + 1 ? 0 : minLength;
  }
}

🧠 코드 풀이

구간 설명

🌊 슬라이딩 윈도우 흐름 예시

입력: target = 7, nums = [2,3,1,2,4,3]

⏱ 시간 & 공간 복잡도

항목 복잡도 설명

✨ 실전 팁 요약

• “조건 만족하는 최소 길이” 문제는 무조건 슬라이딩 윈도우 먼저 떠올릴 것
• 오른쪽으로 확장하면서 합을 만들고, 왼쪽을 줄여가며 최소 길이 갱신
• 투 포인터 + 조건 기반 줄이기 전략은 여러 문제에 응용 가능

LeetCode, Dart 알고리즘, 슬라이딩 윈도우, 투 포인터, 부분합 문제

물통에 가장 많은 물을 담는 방법은?
LeetCode의 11번 문제 "Container With Most Water"는 그리디한 사고와 투 포인터 알고리즘을 적절히 활용할 수 있는 대표 문제입니다.

이 글에서는 Dart로 문제를 풀이하며,
왜 투 포인터가 최적인지,
어떻게 중복 계산 없이 최대값을 구하는지
명확히 설명합니다.

📘 문제 요약

• height[i]는 위치 i에서 세운 수직선의 높이입니다.
• 두 선을 골라, 그 사이를 x축으로 막아 생기는 컨테이너의 물 저장 용량을 구해야 합니다.
• 조건: 컨테이너는 기울일 수 없습니다.

🚀 핵심 아이디어: 투 포인터 (Two Pointers)

❌ 브루트 포스 접근 (비효율)

int max = 0;
for (int i = 0; i < height.length; i++) {
  for (int j = i + 1; j < height.length; j++) {
    int area = (j - i) * min(height[i], height[j]);
    max = max > area ? max : area;
  }
}

• 시간 복잡도: O(n²)
• → 모든 경우를 비교 = 너무 느림!

✅ 최적화: 투 포인터 전략

import 'dart:math';

class Solution {
  int maxArea(List<int> height) {
    int left = 0, right = height.length - 1, answer = 0;

    while (left < right) {
      int width = right - left;
      int water = width * min(height[left], height[right]);
      answer = max(answer, water);

      if (height[left] < height[right]) {
        left++;  // 더 낮은 쪽을 안쪽으로 이동
      } else {
        right--;
      }
    }

    return answer;
  }
}

💡 왜 투 포인터인가?

• 물의 양 = 너비 × 높이
• 너비는 왼쪽/오른쪽 포인터 거리
• 높이는 둘 중 더 낮은 벽이 기준
• 더 높은 벽은 바꾸지 않고, 낮은 벽을 바꿔야 더 나은 결과 가능

→ 즉, 낮은 쪽을 안쪽으로 이동시키며 최댓값 갱신

🧪 예제 설명

입력: [1,8,6,2,5,4,8,3,7]
→ 최댓값은 49: height[1]=8, height[8]=7, 거리 7 → 7 × 7 = 49

⏱ 복잡도 분석

구분 복잡도

✨ 실전 팁

• 이 문제는 투 포인터 개념을 익히기에 아주 좋아요.
• 리스트의 양 끝에서 출발하여, 내려오면서 갱신하는 방식은 다양한 문제에 응용 가능
• 슬라이딩 윈도우 / 그리디 문제에서도 자주 등장하는 패턴입니다.

🏁 마무리

"Container With Most Water"는 단순해보이지만,
투 포인터의 본질적인 사고법을 배울 수 있는 문제입니다.
이 문제 하나만 확실히 이해해도, 이후 LeetCode 문제에서 유사 패턴을 빠르게 인식하게 됩니다.

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);
  });
});

✅ 시간 및 공간 복잡도

항목 복잡도

✅ 마무리 정리

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

🔗 문제 링크: https://leetcode.com/problems/text-justification/

📌 문제 설명

주어진 단어 배열 words를 최대 너비 maxWidth를 기준으로 **좌우 정렬(fully justified)**된 텍스트로 반환하는 문제입니다.

🔹 요구 조건 요약

• 각 줄은 정확히 maxWidth 길이여야 함
• 단어는 최대한 많이 담고, 단어 사이 공백을 균등하게 분배
• 공백이 남을 경우 왼쪽부터 한 칸씩 더 추가
• 마지막 줄은 왼쪽 정렬(left-justified), 단어 사이 공백은 하나씩만, 나머지는 오른쪽에 채움

✅ 풀이 아이디어 (그리디 + 정렬)

1. line: 현재 줄에 넣을 단어들
2. width: 현재 줄의 총 단어 길이
3. 단어를 추가하면서 maxWidth를 초과하면 한 줄 완성 → 공백을 분배하여 정렬
4. 마지막 줄은 예외 처리 (왼쪽 정렬)

✅ 구현 코드 (TypeScript)

export function fullJustify(words: string[], maxWidth: number): string[] {
  const answer: string[] = [];
  let line: string[] = [];
  let width = 0;

  for (const word of words) {
    if (width + word.length + line.length > maxWidth) {
      const totalSpaces = maxWidth - width;
      const gaps = line.length - 1;

      if (gaps === 0) {
        answer.push(line[0] + " ".repeat(totalSpaces));
      } else {
        const space = Math.floor(totalSpaces / gaps);
        const extra = totalSpaces % gaps;
        let row = "";
        for (let i = 0; i < line.length; i++) {
          row += line[i];
          if (i < gaps) {
            row += " ".repeat(space + (i < extra ? 1 : 0));
          }
        }
        answer.push(row);
      }

      line = [];
      width = 0;
    }

    line.push(word);
    width += word.length;
  }

  // 마지막 줄은 왼쪽 정렬
  const lastLine = line.join(" ");
  answer.push(lastLine + " ".repeat(maxWidth - lastLine.length));

  return answer;
}

✅ 예시 시각화 (행 단위 구조 파악용)

입력: ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth: 16

단계별 정렬:

["This    is    an"]   // 단어 3개, 공백 2칸씩 + 1칸 앞쪽
["example  of text"]   // 공백 1칸씩 균등 배분
["justification.  "]   // 마지막 줄, 왼쪽 정렬 + 오른쪽 공백 패딩

각 줄의 길이는 정확히 16이고, 공백 분배가 조건에 맞춰 처리됨

🧪 테스트 코드 (Jest)

describe("LeetCode 68: Text Justification", () => {
  it("formats multiple lines with full justification", () => {
    const input = ["This", "is", "an", "example", "of", "text", "justification."];
    const result = fullJustify(input, 16);
    expect(result).toEqual([
      "This    is    an",
      "example  of text",
      "justification.  "
    ]);
  });

  it("handles single word line correctly", () => {
    const input = ["Single"];
    const result = fullJustify(input, 10);
    expect(result).toEqual(["Single    "]);
  });

  it("handles last line with left justification", () => {
    const input = ["last", "line"];
    const result = fullJustify(input, 10);
    expect(result).toEqual(["last line "]);
  });
});

📈 시간 및 공간 복잡도

항목 복잡도

✅ 마무리 정리

• 공백 분배가 핵심: 단어 사이 공간 수(gaps)를 기준으로 균등 분배하고 남은 공백은 왼쪽부터 추가
• 마지막 줄은 예외 처리 필요
• 전형적인 문자열 조작 + 그리디 알고리즘 문제

📌 문제 설명

문자열 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");
  });
});

📈 시간 및 공간 복잡도

항목 복잡도

✅ 마무리 정리

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

[LeetCode] Reverse Words in a String - 문자열 뒤집기 최적화

📌 문제 설명

LeetCode의 "Reverse Words in a String" 문제는 문자열에서 단어들의 순서를 뒤집는 문제입니다.

• 입력: 문자열 s
• 출력: 단어들의 순서를 뒤집되, 단어 사이의 공백은 하나로 유지해야 함

🔹 예제

입력: "  the   sky is  blue  "
출력: "blue is sky the"

✅ 앞뒤 공백 제거 및 연속된 공백을 하나로 변환해야 함!

📌 초기 접근 방식 (문자열 직접 연결)

처음에는 + 연산을 이용해 단어를 answer 앞에 추가하는 방식으로 구현할 수 있습니다.

export function reverseWords(s: string): string {
  let word = "";
  let answer = "";

  for (const c of s) {
    if (c === " ") {
      if (word.length > 0) {
        answer = answer.length === 0 ? word : word + " " + answer;
        word = "";
      }
    } else {
      word += c;
    }
  }
  if (word.length > 0) {
    answer = word + " " + answer;
  }
  return answer;
}

✅ 작동하지만, O(N^2)로 비효율적! ❌

📌 최적화 1 - 배열 활용 (O(N) 개선)

배열을 활용하면 문자열 연결 연산을 최소화하여 O(N)으로 최적화할 수 있습니다.

export function reverseWords(s: string): string {
  const words: string[] = [];
  let word = "";

  for (const c of s) {
    if (c === " ") {
      if (word.length > 0) {
        words.unshift(word);
        word = "";
      }
    } else {
      word += c;
    }
  }

  if (word.length > 0) {
    words.unshift(word);
  }

  return words.join(" ");
}

✅ 문자열 연결을 최소화하여 O(N) 성능 개선 🚀

📌 최적화 2 - 내장 메서드 활용 (가장 간결한 방법)

JavaScript의 split(), trim(), reverse(), join()을 활용하면 코드가 훨씬 간결해집니다.

export function reverseWords(s: string): string {
  return s.trim().split(/\s+/).reverse().join(" ");
}

🚀 최적화 포인트

1. trim() → 앞뒤 공백 제거
2. split(/\s+/) → 연속된 공백을 하나로 처리하여 단어 배열 생성
3. reverse() → 배열의 단어 순서를 뒤집음
4. join(" ") → 단어를 하나의 공백으로 연결

✅ 최적의 코드! O(N) 복잡도로 간결하게 해결 가능! 🚀

📌 테스트 코드

describe("Reverse Words in a String", () => {
  it("should reverse words correctly", () => {
    expect(reverseWords("  the   sky is  blue  ")).toEqual("blue is sky the");
    expect(reverseWords(" hello world ")).toEqual("world hello");
    expect(reverseWords("a good   example")).toEqual("example good a");
  });
});

✅ 여러 케이스를 테스트하여 정확성 검증!

📌 시간 복잡도 분석

방법 시간 복잡도 설명

✅ 최적화된 코드를 사용하면 성능을 개선할 수 있음! 🚀

📌 최종 정리

1. 문자열을 직접 수정하는 방식은 비효율적이므로 피해야 함
2. 배열을 활용하면 성능이 O(N)으로 최적화 가능
3. 내장 메서드 (split(), reverse(), join())를 활용하면 가장 간결한 코드 작성 가능

💡 비슷한 문제를 만나면 문자열을 배열로 변환한 후 처리하는 방식을 고려해 보세요! 🚀