[leetcode 매일 풀기] 68. text justification

 

오늘 리뷰할 문제는 68.text justification 입니다. https://leetcode.com/problems/text-justification/

Text Justification - LeetCode

 

문제 설명을 하자면

단어들의 리스트와, 최대길이가 주어졌을 때, 해당 단어들을 규칙에 따라 최대길이를 넘지 않게 배치시키는 알고리즘을 작성하는 것이다.

규칙을 나열해보자면

 

1. 단어 사이에는 최소한 한개의 간격이 존재해야 한다.

2. 다음단어가 들어가지 못하는 경우, 빈 공간은 단어 사이의 공간에 최대한 균일하게 분배해야 한다. 균일하게 분배하는게 어렵다면, 앞쪽 공백부터 채운다.

3. 마지막 줄은 공백을 사이에 채우지 않는다.

 

simulation을 해야만 되기 때문에, 단어 목록을 앞에서부터 순회하면서 결과를 만들도록 구현했다.

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:

        results = []
        current_words = []
        current_min_length = 0

        def words_to_string(target_words: List[str]) -> str:
            if len(target_words) == 1:
                return f"{target_words[0]}{' ' * (maxWidth - len(target_words[0]))}"
            num_space = len(target_words) - 1
            space_length = maxWidth - sum(len(w) for w in target_words)
            default_space = space_length // num_space
            extra_space = space_length % num_space

            result_string = ""
            for i, w in enumerate(target_words):
                result_string += w
                if i != len(target_words) - 1:
                    result_string += " " * default_space
                    if extra_space:
                        result_string += " "
                        extra_space -= 1
            return result_string

        for word in words:
            if len(current_words) == 0:
                expected_min_length = current_min_length + len(word)
            else:
                expected_min_length = current_min_length + len(word) + 1

            if expected_min_length > maxWidth:
                results.append(words_to_string(current_words))
                current_words = []
                current_min_length = len(word)
            else:
                current_min_length = expected_min_length

            current_words.append(word)

        if current_words:
            results.append(
                " ".join(current_words) + " " * (maxWidth - current_min_length)
            )

        return results


assert Solution().fullJustify(
    ["This", "is", "an", "example", "of", "text", "justification."], 16
) == [
    "This    is    an",
    "example  of text",
    "justification.  ",
]
assert Solution().fullJustify(
    ["What", "must", "be", "acknowledgment", "shall", "be"], 16
) == [
    "What   must   be",
    "acknowledgment  ",
    "shall be        ",
]
assert Solution().fullJustify(
    [
        "Science",
        "is",
        "what",
        "we",
        "understand",
        "well",
        "enough",
        "to",
        "explain",
        "to",
        "a",
        "computer.",
        "Art",
        "is",
        "everything",
        "else",
        "we",
        "do",
    ],
    20,
) == [
    "Science  is  what we",
    "understand      well",
    "enough to explain to",
    "a  computer.  Art is",
    "everything  else  we",
    "do                  ",
]

 

20분정도 투자했더니, 위의 구현이 나왔고, 제출결과는 다음과 같았다.

 

다른 사람의 코드를 봤을 때, 알고리즘은 큰 차이는 없어보였다.