[LeetCode] 68. Text Justification

 

https://leetcode.com/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150 

Text Justification - LeetCode

문제 유형 : 문자열 처리 / 그리디

문제 난이도 : Hard

 

문제

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.

문자열 배열 words와 넓이 maxWidth가 주어진다.

아래의 규칙으로 재배열하여 반환하시오:

 

1. 한 줄에 maxWidth의 길이를 넘지 않도록 단어를 나누고, 남은 칸은 단어 사이를 최대한 균일하게 공백으로 채운다.

2. 마지막줄은 왼쪽으로 단어를 정렬시키고, 단어 간의 공백은 한칸으로 둔다.

 

풀이

한 줄에 들어가는 단어들의 길이를 저장하기 위한 변수를 만들고,

maxWidth를 넘기 직전까지 단어 인덱스를 늘려간다.

 

maxWidth에 최대로 커진 변수를 뺴서 남은 공백칸을 구하고,

나눗셈과 나머지 연산을 이용하여 각 칸에 공백을 얼마나 넣을지 구한다.

 

한 문장을 담을 빈 문자열을 선언하여 시작 단어들부터 끝 단어들까지 주어진 공백에 맞게 간격을 벌리며 넣어준다.

마지막 문장이라면(인덱스가 최대로 도달하면) 단어들간의 사이는 한칸으로, 뒤 나머지 공간은 모두 공백으로 채워준다.

 

코드

C++

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        const int n = words.size();
        vector<string> result;
        int i = 0;
    
        while (i < n) {
            int j = i + 1;
            int lineLength = words[i].size();
            while (j < n && (lineLength + words[j].size() + (j - i - 1)) < maxWidth) {
                lineLength += words[j++].size();
            }
        
            int diff = maxWidth - lineLength;
            int numberOfWords = j - i;
            if (numberOfWords == 1 || j == n) { // 마지막 문장인 경우, 다른 방식으로 문자열을 삽입
                result.push_back(words[i]);
                for (int k = i + 1; k < j; ++k) {
                    result.back() += " " + words[k];
                }
                result.back() += string(diff - (j - i - 1), ' ');
            } else {
                int spaces = diff / (numberOfWords - 1);
                int extra = diff % (numberOfWords - 1);
                result.push_back(words[i]);
                for (int k = i + 1; k < j; ++k) {
                    result.back() += string(spaces + ((k - i) <= extra ? 1 : 0), ' ') + words[k];
                }
            }
            i = j;
        }
        return result;
    }
};

 

Python3

 

def fullJustify(words, maxWidth):
    res, cur, num_of_letters = [], [], 0
    for w in words:
        if num_of_letters + len(w) + len(cur) > maxWidth:
            for i in range(maxWidth - num_of_letters):
                cur[i%(len(cur)-1 or 1)] += ' '
            res.append(''.join(cur))
            cur, num_of_letters = [], 0
        cur += [w]
        num_of_letters += len(w)
    return res + [' '.join(cur).ljust(maxWidth)]

 

Dart

List<String> fullJustify(List<String> words, int maxWidth) {
  List<String> result = [];
  int i = 0, n = words.length;

  while (i < n) {
    int j = i + 1;
    int lineLength = words[i].length;
    while (j < n && (lineLength + words[j].length + (j - i - 1)) < maxWidth) {
      lineLength += words[j++].length;
    }

    int diff = maxWidth - lineLength;
    int numberOfWords = j - i;
    if (numberOfWords == 1 || j == n) {
      result.add(words[i]);
      for (int k = i + 1; k < j; ++k) {
        result[result.length - 1] += " " + words[k];
      }
      result[result.length - 1] += " " * (diff - (j - i - 1));
    } else {
      int spaces = diff ~/ (numberOfWords - 1);
      int extra = diff % (numberOfWords - 1);
      result.add(words[i]);
      for (int k = i + 1; k < j; ++k) {
        result[result.length - 1] += " " * (spaces + ((k - i) <= extra ? 1 : 0)) + words[k];
      }
    }
    i = j;
  }
  return result;
}

 

Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int len = words.length;
        List<String> lines = new ArrayList<String>();
        int index = 0;

        while (index < len) {
            int totalChars = words[index].length();
            int last = index + 1;
            while (last < len) {
                if (totalChars + 1 + words[last].length() > maxWidth) break;
                totalChars += 1 + words[last].length();
                last++;
            }
            
            int gapLen = last - index - 1;
            StringBuilder sb = new StringBuilder();
            if (last == len || gapLen == 0) {
                for (int i = index; i < last; i++) {
                    sb.append(words[i]);
                    sb.append(' ');
                }
                sb.deleteCharAt(sb.length() - 1);
                for (int i = sb.length(); i < maxWidth; i++) {
                    sb.append(' ');
                }
            } else {
                int spaces = (maxWidth - totalChars) / gapLen;
                int r = (maxWidth - totalChars) % gapLen;
                for (int i = index; i < last; i++) {
                    sb.append(words[i]);
                    sb.append(' ');
                    if (i < index + r) sb.append(' ');
                    if (i < last - 1) for (int j = 0; j < spaces; j++) sb.append(' ');
                }
            }
            lines.add(sb.toString());
            index = last;
        }

        return lines;
    }
}

 

swift

func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
    var lines = [String]()
    var width = maxWidth
    var lineWords = [String]()
    
    for word in words {
        if width < word.count {
            lines.append(justify(lineWords, width + lineWords.count))
            lineWords = [word]
            width = maxWidth - word.count
        } else {
            lineWords.append(word)
            width -= word.count + 1
        }
    }
    
    let lastLine = lineWords.joined(separator: " ")
    lines.append(lastLine + String(repeating: " ", count: maxWidth - lastLine.count))
    
    return lines
}

func justify(_ words: [String], _ maxWidth: Int) -> String {
    var gap = words.count - 1
    var spaces = maxWidth - words.reduce(0) { $0 + $1.count }
    
    var res = words.reduce("") { result, word in
        if gap > 0 {
            let quotient = spaces / gap
            let remainder = spaces % gap
            let spaceCount = quotient + (remainder > 0 ? 1 : 0)
            spaces -= spaceCount
            gap -= 1
            return result + word + String(repeating: " ", count: spaceCount)
        } else {
            return result + word
        }
    }
    res += String(repeating: " ", count: maxWidth - res.count)
    
    return res
}