[LeetCode 68] Text Justification - 텍스트 양쪽 정렬

🔗 문제 링크: 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 "]);
  });
});

---

📈 시간 및 공간 복잡도

항목 복잡도

시간	O(N) (단어 수 N)
공간	O(N) (결과 줄 수 만큼)

---

✅ 마무리 정리

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