수달씨의 개발공간

[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())를 활용하면 가장 간결한 코드 작성 가능

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