리트코드 - 68. Text Justification

리트코드 - 68. Text Justification

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

 

문제 설명

문자열 배열 words와 너비 maxWidth가 주어졌을 때, 각 줄이 정확히 maxWidth 문자를 갖도록 텍스트를 포맷하되, 완전히 (왼쪽과 오른쪽으로) 정렬되어야 합니다.

즉, 가능한 한 많은 단어를 각 줄에 넣는 탐욕적 접근 방식을 사용해야 합니다. 필요한 경우 추가 공백 ' '을 삽입하여 각 줄이 정확히 maxWidth 문자를 갖도록 해야 합니다.

단어 사이의 추가 공백은 가능한 한 균등하게 분배되어야 합니다. 한 줄에 단어 사이의 공백 수가 균등하게 나누어지지 않는 경우, 왼쪽의 빈 칸에 더 많은 공백이 할당되어야 합니다.

텍스트의 마지막 줄은 왼쪽 정렬되어야 하며, 단어 사이에 추가 공백이 삽입되어서는 안 됩니다.

참고 사항:

• 단어는 공백 문자가 아닌 문자 시퀀스로 정의됩니다.
• 각 단어의 길이는 0보다 크고 maxWidth를 초과하지 않는 것이 보장됩니다.
• 입력 배열 words는 최소한 하나의 단어를 포함합니다.

풀이코드

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> res = new ArrayList<>();
        List<String> line = new ArrayList<>();
        int wordsLen = 0;
        int spaces = 0 ;
        int remain = 0;
        int lastRowSpace = 0;
        String lastLine = "";
        StringBuilder lineStr;

        for (String word : words) {
            int fullLen = wordsLen + line.size() - 1; // 단어길이 + 최소의 공백을 포함한 길이

            if (fullLen + word.length() + 1 > maxWidth) {
                spaces = (maxWidth - wordsLen) / Math.max(1, line.size() - 1); // 0으로 나눠지는 것을 방지하기 위함.
                remain = (maxWidth - wordsLen) % Math.max(1, line.size() - 1);

                lineStr = new StringBuilder();

                for (int j = 0; j < line.size(); j++) {
                    lineStr.append(line.get(j));

                    if (line.size() == 1) {
                        lineStr.append(" ".repeat(spaces));
                    }

                    if (j < line.size() - 1) { // 마지막 단어 전까지만 공백을 더함
                        int spaceToAppend = spaces; // 기본 공백 추가
                        if (remain > 0) {
                            spaceToAppend += 1; // remain이 남아있으면 공백 하나 추가
                            remain--; // 추가한 후에는 remain 감소
                        }

                        lineStr.append(" ".repeat(spaceToAppend));
                    }
                }
                res.add(lineStr.toString());
                line.clear();
                wordsLen = 0;
            }

            line.add(word);
            wordsLen += word.length();
        }

        // 마지막 줄 처리
        lastLine = String.join(" ", line);
        lastRowSpace = maxWidth - lastLine.length();
        res.add(lastLine + " ".repeat(lastRowSpace));

        return res;
    }
}

코드설명

문제의 설명을 한 문장으로 정리해보면, 특정 길이 안에 주어진 단어를 최대한 많이 넣는 것이다.

이를 다시 세부적으로 나누어보면 마지막 줄이 아닌 경우와 마지막 줄인 경우로 나누어야 한다.

 

1.  먼저 마지막 줄이 아닌 경우, 단어가 1개만 들어갈 때와 1개 이상일 때로 나누어서 생각해야 한다.
   단어가 1개만 들어왔다면, 뒷부분에 남은 공백으로 채워진다.
   단어가 2개 이상이 들어온 경우, 처음과 끝은 단어로 끝나야 하고 중간에 공백으로 채워야한다. 이 공백을 채울 때 갯수가 동일하게 나누어지지 않는다면 제일 처음 단어 뒤에 공백을 하나 추가한다.
2. 마지막 줄인 경우 남은 공백을 단어 제일 뒤에다가 넣어주어야 한다. 단어가 2개 이상이라면 한 칸만 띄워 배치하고 나머지를 제일 뒤에 넣어준다.

이 문제를 풀 때 가장 어려웠던 부분은 단어의 길이를 측정하는 것과 언제 공백을 더해주느냐였다.

단순히 단어의 길이만 측정하면 안되고 공백까지 고려해야 하기 때문이다.

 

여러가지 방법이 있겠지만 문장의 길이가 넘어가는 순간이 트리거 지점이라고 판단되어 아래와 같은 순서로 구상했다.

 

0. 단어를 넣을 line 배열을 만든다. 

1. 단어를 순회한다.

2. 단어 길이의 합 + line 배열의 크기(=최소 띄어쓰기)로 현재 총 길이를 구한다.

3. 현재 단어 길이 + 2번에서 구한 길이 +1 (띄어쓰기)한 값이 요구한 문장 길이보다 커지면, 이 때 단어들을 추가하고 답 배열에 넣은 뒤 line 배열을 비운다.

4. 3의 조건을 만족하지 않은 경우 line 배열에 단어를 추가하고, 단어길이를 누적으로 합해준다.

 

구현 코드를 세부적으로 보며 설명하겠다.

for (String word : words) {
    int fullLen = wordsLen + line.size() - 1; // 단어길이 + 최소의 공백을 포함한 길이
    
    if (fullLen + word.length() + 1 > maxWidth) {
    	...
    }	
    
    line.add(word);
    wordsLen += word.length();
}

 

1~2,4번에서 이야기 한 것처럼 단어를 순회한다.

단어는 for문 마지막에야 더하는데, 단어 길이의 합이 문장 길이를 넘어서는 순간 그 단어는 다음 줄에 첫번째 단어가 될 것이다.

따라서 이 단어 앞에 단어들만 줄에 배치 되어야 하기 때문에 이렇게 구현했다.

if (wordsLen + line.size() > maxWidth) {

 

첫 줄의 fullLen은 가독성을 위하여 추가했는데, 사실 위와 같이 리팩토링 해도 논리적으로 이상한 것은 없다.

여기서 중요한 것은 단어 길이와 공백을 같이 처리하지 않고, 단어 길이는 단어 길이대로 wordsLen으로, 공백은 line.size()를 통해 처리한 것이다.

if (fullLen + word.length() + 1 > maxWidth) {
    spaces = (maxWidth - wordsLen) / Math.max(1, line.size() - 1); // 0으로 나눠지는 것을 방지하기 위함.
    remain = (maxWidth - wordsLen) % Math.max(1, line.size() - 1);

    lineStr = new StringBuilder();

    for (int j = 0; j < line.size(); j++) {
        ...
    }
    res.add(lineStr.toString());
    line.clear();
    wordsLen = 0;
}

이제 3번을 if문 내부에서 처리해야한다. 단어들을 배치하는 방법인데 마지막 줄은 언제든 if (fullLen + word.length() + 1 > maxWidth) 를 만족하지 못한다. 단어 길이+공백 의 합이 maxWidth 보다 클 때만 진입할 수 있기 때문이다.

 

따라서, 마지막 줄은 순회를 다 끝내고 따로 처리하기로 하고, 마지막 줄이 아닌 경우를 처리해야한다.

spaces는 단어와 단어 사이 들어갈 공백 갯수이고, remain은 공백이 딱 나누어 떨어지지 않았을때 남은 공백을 처리하기 위한 것이다.

공백수는 단어수 - 1 이므로 line.size() - 1 로 처리했고, Math.max(1, line.size() -1) 로 처리한 이유는 단어가 한개만 들어가는 경우 0으로 나눌수 없는 ArithmeticException 익셉션이 터지므로 이것을 방지하기 위함이다.

 

이렇게 하고, for문 안에서 단어를 더해준 다음 이걸 정답 배열에 넣고, 단어 배열인 line은 초기화해준다. 마찬가지로 단어 길이도 0으로 초기화해준다.

 

for (int j = 0; j < line.size(); j++) {
    lineStr.append(line.get(j));

    if (line.size() == 1) {
        lineStr.append(" ".repeat(spaces));
    }

    if (j < line.size() - 1) { // 마지막 단어 전까지만 공백을 더함
        int spaceToAppend = spaces; // 기본 공백 추가
        if (remain > 0) {
            spaceToAppend += 1; // remain이 남아있으면 공백 하나 추가
            remain--; // 추가한 후에는 remain 감소
        }

        lineStr.append(" ".repeat(spaceToAppend));
    }
}

이제 for문안에서는 단어들을 더해주면 되는데, 공백은 String에서 제공하는 repeat 메소드를 이용해서 더해주었다.

 

더할 때는 먼저 단어를 더하고, 마지막 단어가 아닌 경우 공백을 더해주는 방식을 선택했다.

공백을 더할 때 동적으로 더하는게 조금 까다로웠는데 예를 들어 남은 공백이 5이고 단어가 4개이면 공백 위치는 3개이다.

그러면 2,2,1  순으로 공백을 더해주게 되는데 이를 for 문 안에서 조건을 걸어 바꾸기가 조금 난감했다.

 

이전에 remain을 구해놓은 것이 있으므로 remain이 0보다 크다면 space에 1을 추가해서 공백을 더하고, remain을 1 빼주는 방법을 선택했다.

 

남은 remain이 없다면 그냥 space 만큼 공백을 더해주면 된다.

 

중간에 if (line.size() ==1) 는 단어가 하나만 들어왔을 때 뒤에 공백을 추가하기 위한 로직이다.

단어가 하나인 경우 첫 단어이자 마지막 단어이므로 공백을 더하지 않기 때문이다.

// 마지막 줄 처리
lastLine = String.join(" ", line);
lastRowSpace = maxWidth - lastLine.length();
res.add(lastLine + " ".repeat(lastRowSpace));

마지막으로 마지막 줄에 대한 처리가 남았다.

마지막 줄은 String.join을 이용해서 단어들을 한 칸씩 띄어 만들어주고, 남은 칸은 뒤에다가 붙여서 해결했다.

 

시간복잡도 - O(N * M) (N은 words 의 크기, M은 제일 긴 단어의 글자수)

공간복잡도 - O(N + M)

 

엄밀히 따지면 위와 같은데, M은 maxWidth에 의해 결정되고, 1 <= maxWidth <= 100 이므로 M은 무시해도 되지 않을까 싶다.

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        List<String> line = new ArrayList<>();
        int wordsLen = 0;
        int spaces = 0 ;
        int remain = 0;
        int lastRowSpaces = 0;
        String lastLine = "";
        StringBuilder lineStr;

        for (String word : words) {
            int fullLen = wordsLen + line.size() - 1; // 단어길이 + 최소의 공백을 포함한 길이

            if (fullLen + word.length() + 1 > maxWidth) {
                spaces = (maxWidth - wordsLen) / Math.max(1, line.size() - 1); // 0으로 나눠지는 것을 방지하기 위함.
                remain = (maxWidth - wordsLen) % Math.max(1, line.size() - 1);
                lineStr = new StringBuilder();
                
                for (int j = 0; j < line.size(); j++) {
                    lineStr.append(line.get(j));
                    if (j < line.size() - 1) { // 마지막 단어 전까지만 공백을 더함
                        int spaceToAppend = spaces; // 기본 공백 추가
                        if (remain > 0) {
                            spaceToAppend += 1; // remain이 남아있으면 공백 하나 추가
                            remain--; // 추가한 후에는 remain 감소
                        }
                        lineStr.append(" ".repeat(spaceToAppend));
                    }
                }
                res.add(lineStr.toString());
                line.clear();
                wordsLen = 0;
            }

            line.add(word);
            wordsLen += word.length();
        }

        // 마지막 줄 처리
        lastLine = String.join(" ", line);
        lastRowSpaces = maxWidth - lastLine.length();
        res.add(lastLine + " ".repeat(lastRowSpaces));

        return res;
    }
}

여러 번의 시행착오 끝에 위와같이 구현했더니 1번 테스트케이스는 통과되었으나 2번을 통과하지 못했다.

 

이유는 뭔지 알겠는데 어디에 추가해서 처리해야 할까 이곳 저곳 많이 넣어서 시도해봤다가, 구현 코드에서처럼 두번째 for문에서 단어를 더한다음 뒤에서 바로 더하게끔 구현했다.

 

정리

한정된 공간 내에서 단어를 최대한 많이 배치하는 방법