[Algorithm] Leetcode - Text Justification

조건

1. 전체 단어배열을 받고, 하나의 줄의 길이를 input으로 받아서 조건에 맞는 문자열 배열을 반환한다

2. 예제를 통해서 조건을 살펴보자

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

   • "This", "is", "an", “example” 글자는 총 15글자이기 때문에 첫번째 줄에 들어갈수 있을 것 같지만 모든 단어와 단어 사이에는 기본적으로 “ ” space가 들어가야 하기 때문에 최대 글자수 16을 넘어서 "This", "is", "an" 까지만 들어간다
   • "example of text" 두번째 줄에서 첫번째 띄어쓰기 에서는 “ ” space 가 두개, 두번째 띄워쓰기 에서는 “ ” space 가 한개인것을 확인할 수 있다. 이거는
     • 한줄에 글자가 두개이상일때는 반드시 마지막 글자는 오른쪽 정렬 되어있어야 한다는 규칙이 있기 때문이다
     • 그래서 16개의 char를 넣을 수 있는데 총 example of text 이렇게 3개의 단어를 넣으면 총 13개의 공간을 차지하고, 3개의 띄어쓰기 공간이 남는데
     • 이때, 오른쪽으로 갈수록 띄어쓰기 공간은 줄어들어야 한다.
     • 예를들어 가 띄어쓰기라고 할 때 `“exampleoftext”는 될수가 없고“exampleof*text”` 가 되어야 한다는 말이다
   • 마지막줄은 반드시 왼쪽정렬이 되어있어야 한다

구현

package algorithmn.textJustification;

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

public class Solution {
    public static List<String> fullJustify(String[] words, int maxWidth) {
        List<List<String>> outString = new ArrayList<>();
        List<List<Integer>> outNumSpace = new ArrayList<>();

        justifyRecursive(0, words, outString, outNumSpace, maxWidth);

        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < outString.size() - 1; ++i) {
            List<String> line = outString.get(i);
            List<Integer> numSpaces = outNumSpace.get(i);

            sb.append(line.get(0));

            for (int j = 1; j < line.size(); ++j) {
                int space = numSpaces.get(j - 1);
                String word = line.get(j);

                sb.append(" ".repeat(Math.max(0, space)));
                sb.append(word);
            }

            // add padding
            int padding = maxWidth - sb.length();
            sb.append(" ".repeat(Math.max(0, padding)));

            result.add(sb.toString());
            sb.setLength(0);
        }

        sb.setLength(0);

        List<String> lastLine = outString.get(outString.size() - 1);
        sb.append(lastLine.get(0));
        for (int i = 1; i < lastLine.size(); ++i) {
            sb.append(" ");
            sb.append(lastLine.get(i));
        }

        // add padding
        int padding = maxWidth - sb.length();
        sb.append(" ".repeat(Math.max(0, padding)));

        result.add(sb.toString());

        return result;
    }

    private static void justifyRecursive(int start, String[] words, List<List<String>> outString, List<List<Integer>> outNumSpace, int maxWidth) {
        if (start > words.length - 1) {
            return;
        }

        List<String> line = new ArrayList<>();
        int i;

        int lenMust = 0;
        int lenOnlyWords = 0;

        for (i = start; i < words.length; ++i) {
            String cur = words[i];
            if (lenMust + cur.length() > maxWidth) {
                --lenMust;
                break;
            }
            line.add(cur);
            lenMust += cur.length() + 1;
            lenOnlyWords += cur.length();
        }

        List<String> strings = new ArrayList<>();
        List<Integer> numSpaces = new ArrayList<>();

        if (line.size() < 2) {
            String word = line.get(0);
            strings.add(word);
            numSpaces.add(maxWidth - word.length());
        } else {
            int leftWidth = maxWidth - lenOnlyWords;
            int leftWidthActual = 0;

            int numSpace = leftWidth / (line.size() - 1);
            leftWidthActual = numSpace * (line.size() - 1);

            strings.add(line.get(0));
            for (int j = 1; j < line.size() - 1; ++j) {
                String word = line.get(j);
                numSpaces.add(numSpace);
                strings.add(word);
            }

            if (leftWidth != leftWidthActual) {
                int offset = leftWidth - leftWidthActual;
                int j = 0;
                while (offset != 0) {
                    numSpaces.set(j, numSpaces.get(j) + 1);
                    --offset;
                    ++j;
                }
            }

            numSpaces.add(numSpace);
            strings.add(line.get(line.size() - 1));
        }

        outString.add(strings);
        outNumSpace.add(numSpaces);

        justifyRecursive(i, words, outString, outNumSpace, maxWidth);
    }
}

• 분할정복으로 풀어야 한다고 생각해서 하위 문제가 다른 외부 조건에 영향을 받지 않도록 했다
• 마지막줄은 왼쪽정렬이기 때문에 다른 줄을 만들때와는 푸는 방법이 다르다.
  • 하지만 줄이 n개로 계속 늘어나도 마지막줄은 하나이기 때문에 마지막줄 처리부분만 추가해주면 되어서 모든 줄을 하나의 문제로 풀수있게 끔 만들었다
• 한줄에에 단어가 두개 이상이라면 반드시 단어 + 스페이스 가 짝을 이루어야 한다.(줄의 마지막 글자 제외) 그래서 단어 + 스페이스 를 하나의 단위로 보고 줄 안에 들어갈 단어를 판단했다.
• 하나의 줄 안에 들어갈 단어가 정해지면 단어와 단어 사이에 스페이스를 얼마나 넣을지 정하는 방법은 다음과 같다
  • 단어가 2개 이상일 때, 단어가 n개 있으면 whitespace 개수는 n - 1 개 이다.
  • (한 줄에 들어갈 문자개수(maxWidth) - 총 단어 문자개수의 합) / n - 1 = 단어 사이에 들어갈 white space 개수 - A
  • 이렇게 되는데 / 연산은 소수점 뒤에 자리를 버리는 연산이다.
    • 예를들어서 do for you ask 이런 줄이 있고, 한줄에 16개의 단어만 들어갈수 있다.
    • 순수 단어들의 길이는 11이고, 한줄에는 16이 들어갈수 있기 때문에 5을 whitespace 로 반드시 채워야 한다
    • 하지만 (한 줄에 들어갈 문자개수(maxWidth) - 총 단어 문자개수의 합) / n - 1 = 단어 사이에 들어갈 white space 개수 식에 의하면 (16 - 11) 나누기 3 = 1.6666.. 이나와서 0.6666.. 부분은 버려서 1만 남는다
    • 그 결과 whitespace에 1 * 3 = 3 만큼의 스페이스만 들어가기 때문에 2의 공간을 채울수가 없게 된다
  • 이걸 이런 경우에 남은 2의 공간을 채우기 위해서 leftWidth 와 leftWidthActual 변수를 두개 사용했다

    if (leftWidth != leftWidthActual) {
        int offset = leftWidth - leftWidthActual;
        int j = 0;
        while (offset != 0) {
            numSpaces.set(j, numSpaces.get(j) + 1);
            --offset;
            ++j;
        }
    }
    // offset distribution을 수행하는 부분

    • leftWidth 에는 (한 줄에 들어갈 문자개수(maxWidth) - 총 단어 문자개수의 합) 의 결과가 저장되고,
    • leftWidthActual 에는 A * (n - 1) 을 계산한, 실제 A식에 의해서 채워지는 whitespace의 개수를 저장한다.
    • 그래서 leftWidth 와 leftWidthActual 의 offset 만큼, 왼쪽에 있는 whitespace 부터 1씩 더해서 적용시켜준다
    • leftWidth > 2 * leftWidthActual 를 반드시 만족하기 때문에 최대 n - 1 번의 offset distribution 을 수행하면 된다
• 마지막에 List<List<String>> outString, List<List<Integer>> outNumSpace 에 담긴 줄에 들어간느 문자들과, 줄에 들어가는 whitespace 들을 조합해서 justification 이 적용된 배열을 만들어 리턴한다