[LeetCode] 68. Text Justification

단어 사이에 공백을 균일하게 두는 것을 목표로 하는 문제이다.

유의해야할 포인트는 다음과 같다.

1. maxWidth보다 짧은 문자열을 만들되, 최대한 많은 단어가 들어갈 것
2. 공백의 수를 동일하게 만들 수 없다면, 문자열에 좌측 공백부터 우선적으로 보충할 것
3. 하나의 단어 혹은 마지막 행의 문자열의 경우 좌측 정렬 후 우측을 모두 공백으로 채울 것

😎풀이

function fullJustify(words: string[], maxWidth: number): string[] {
    const result = [];
    let curLine = [];
    let curLen = 0;

    for (const word of words) {
        const wordLen = word.length;
        // 현재 줄에 단어를 추가할 수 있는지 확인
        // curLine.length는 필요한 최소 공백 수
        if (wordLen + curLen + curLine.length <= maxWidth) {
            curLen += wordLen;
            curLine.push(word);
        } else {
            // 현재 줄을 정렬하고 결과에 추가
            const newLine = justifyLine(curLine, maxWidth, curLen, false);
            result.push(newLine);
            curLine = [word];
            curLen = wordLen;
        }
    }

    // 마지막 줄 처리 (왼쪽 정렬)
    const lastLine = justifyLine(curLine, maxWidth, curLen, true);
    result.push(lastLine);

    return result;
}

function justifyLine(curLine: string[], maxWidth: number, curLen: number, isLastLine: boolean): string {
    const lineLen = curLine.length;
    
    // 마지막 줄이거나 단어가 하나뿐인 경우 왼쪽 정렬
    if (isLastLine || lineLen === 1) {
        return curLine.join(' ') + ' '.repeat(maxWidth - curLen - (lineLen - 1));
    }

    const totalGap = maxWidth - curLen;
    const gapDivisor = lineLen - 1;
    const wordGap = Math.floor(totalGap / gapDivisor);
    let remainGap = totalGap % gapDivisor;

    let newLine = "";
    for (let i = 0; i < lineLen - 1; i++) {
        newLine += curLine[i];
        // 기본 간격에 추가 간격을 더하여 공백 추가
        const spaces = wordGap + (remainGap > 0 ? 1 : 0);
        newLine += ' '.repeat(spaces);
        if (remainGap > 0) remainGap--;
    }
    newLine += curLine[lineLen - 1]; // 마지막 단어 추가

    return newLine;
}