[LeetCode] 68. Text Justification

https://leetcode.com/

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

 

Note:

• A word is defined as a character sequence consisting of non-space characters only.
• Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
• The input array words contains at least one word.

Example 1:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

 

Example 2:

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output: 
[
   "What must be",
   "acknowledgment ",
   "shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word.

 

Example 3:

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
   "Science is what we",
   "understand well",
   "enough to explain to",
   "a computer. Art is",
   "everything else we",
   "do "
]

 

Constraints:

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] consists of only English letters and symbols.
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

Code:

var fullJustify = function(words, maxWidth) {
    const result = []; // 결과를 저장할 배열
    let line = []; // 현재 처리중인 줄의 단어들을 저장할 배열
    let lineLength = 0; // 현재 처리중인 줄의 길이

    for (let i = 0; i < words.length; i++) { // 단어 배열을 반복
        if (lineLength + line.length + words[i].length > maxWidth) { // 만약 현재 줄에 단어를 추가했을 때 maxWidth를 초과한다면
            const numSpaces = maxWidth - lineLength; // 공백의 개수를 계산
            const numGaps = line.length - 1 || 1; // 공백을 삽입할 간격의 개수를 계산

            let lineStr = line[0]; // 결과로 저장할 현재 줄의 문자열 초기화

            if (line.length === 1) { // 현재 줄에 단어가 하나만 있다면
                lineStr += ' '.repeat(numSpaces); // 공백을 삽입
            } else { // 현재 줄에 단어가 여러 개 있다면
                const spaces = ' '.repeat(Math.floor(numSpaces / numGaps)); // 간격마다 삽입할 공백 문자열을 생성
                const extraSpaces = numSpaces % numGaps; // 추가로 삽입할 공백의 개수를 계산
                for (let j = 1; j < line.length; j++) { // 현재 줄의 단어들을 순회하면서
                    if (j <= extraSpaces) { // 추가로 삽입할 공백이 남아있다면
                        lineStr += spaces + ' ' + line[j]; // 해당 위치에 공백을 삽입하여 단어를 연결
                    } else {
                        lineStr += spaces + line[j]; // 아니면 공백 없이 단어를 연결
                    }
                }
            }

            result.push(lineStr); // 완성된 현재 줄을 결과 배열에 삽입
            line = []; // 현재 줄을 초기화
            lineLength = 0; // 현재 줄의 길이를 초기화
        }

        line.push(words[i]); // 현재 단어를 현재 줄에 삽입
        lineLength += words[i].length; // 현재 단어의 길이를 현재 줄의 길이에 추가
    }

    result.push(line.join(' ').padEnd(maxWidth, ' ')); // 마지막 줄에 대한 처리를 마무리하고 결과 배열에 삽입
    return result; // 결과 배열 반환
};

 

Solutions Code :

// Solution 1
var fullJustify = function(words, maxWidth) {
    // 결과를 저장할 배열 선언
    let res = [];
    // 현재 줄의 단어들을 저장할 배열
    let cur = [];
    // 현재 줄에 포함된 글자 수
    let num_of_letters = 0;
    // 주어진 단어 배열을 순회하며 처리
    for (let word of words) {
        // 현재 단어를 추가했을 때 너비를 초과하는 경우
        if (word.length + cur.length + num_of_letters > maxWidth) {
            // 단어 사이에 공백을 삽입하여 maxWidth에 맞도록 조정
            for (let i = 0; i < maxWidth - num_of_letters; i++) {
                // 단어 간 공백을 균등하게 분배 (나머지 공백은 앞쪽 단어들에 추가)
                cur[i % (cur.length - 1 || 1)] += ' ';
            }
            // 현재 줄을 결과 배열에 추가
            res.push(cur.join(''));
            // 현재 줄과 글자 수 초기화
            cur = [];
            num_of_letters = 0;
        }
        // 현재 단어를 현재 줄에 추가
        cur.push(word);
        // 현재 단어의 길이를 더함
        num_of_letters += word.length;
    }
    // 마지막 줄 처리: 남은 공간에 공백을 추가하여 maxWidth에 맞게 조정
    let lastLine = cur.join(' ');
    while (lastLine.length < maxWidth) lastLine += ' ';
    // 결과 배열에 마지막 줄 추가
    res.push(lastLine);
    // 결과 배열 반환
    return res;
};

// Solutions 2
var fullJustify = function(words, maxWidth) {
    // 결과를 저장할 배열 선언
    let res = [];
    // 현재 줄에 포함된 단어들을 저장할 배열
    let curWords = [];
    // 현재 줄에 포함된 모든 글자 수
    let curLen = 0;
    // 주어진 단어 배열을 순회하며 처리
    for (let word of words) {
        // 현재 단어를 추가했을 때 너비를 초과하는 경우
        if (curLen + word.length + curWords.length > maxWidth) {
            // 현재 줄에 채울 추가적인 공백 계산
            let totalSpaces = maxWidth - curLen;
            // 현재 줄에 포함된 단어들 사이의 간격 개수
            let gaps = curWords.length - 1;
            // 간격이 하나인 경우 (한 단어만 있는 경우)
            if (gaps === 0) {
                // 해당 줄을 결과 배열에 추가하고 공백 삽입하여 maxWidth에 맞도록 조정
                res.push(curWords[0] + ' '.repeat(totalSpaces));
            } else {
                // 각 간격에 분배될 공백 수 계산
                let spacePerGap = Math.floor(totalSpaces / gaps);
                // 추가적인 공백이 필요한 간격의 수 계산
                let extraSpaces = totalSpaces % gaps;
                // 줄을 구성할 문자열 초기화
                let line = '';
                // 현재 줄에 포함된 단어들을 순회하면서 줄을 구성
                for (let i = 0; i < curWords.length; i++) {
                    // 단어 추가
                    line += curWords[i];
                    // 마지막 단어가 아니라면 간격에 공백 추가
                    if (i < gaps) {
                        line += ' '.repeat(spacePerGap);
                        // 추가적인 공백이 필요한 경우 해당 간격에 추가 공백 삽입
                        if (i < extraSpaces) {
                            line += ' ';
                        }
                    }
                }
                // 완성된 줄을 결과 배열에 추가
                res.push(line);
            }
            // 현재 줄과 글자 수 초기화
            curWords = [];
            curLen = 0;
        }
        // 현재 단어를 현재 줄에 추가하고 글자 수 업데이트
        curWords.push(word);
        curLen += word.length;
    }
    // 마지막 줄 처리: 남은 공간에 공백을 추가하여 maxWidth에 맞게 조정
    let lastLine = curWords.join(' ');
    while (lastLine.length < maxWidth) {
        lastLine += ' ';
    }
    // 결과 배열에 마지막 줄 추가
    res.push(lastLine);
    // 결과 배열 반환
    return res;
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode