LeetCode: 68번 (Text Justification) [JAVA]

문제 링크

https://leetcode.com/problems/text-justification/

Text Justification - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 반복문을 통해 하나의 문자열로 만들어낼 수 있는 단어들의 집합을 생성
2. 단어의 집합과 조건들을 바탕으로 문자열을 생성
   1) 단어 집합에 단어가 하나만 있는 경우
   2) 현재 단어의 집합이 마지막 라인의 줄인 경우
   3) 그 외 케이스
3. 결과 List<String>을 반환

 단순한 구현 문제이다. 문제에서 주어진 단어들을 바탕으로, 최대한 한 줄에 단어들을 많이 포함하는 문자열을 만들어야 한다. 이 때 추가적으로 주어진 maxWidth에 길이가 맞게 문자열을 만들어야 하며, 그 과정에서 단어들 사이 공백들의 길이가 최대한 고르게 퍼져야 한다.
 이를 해결하기 위해 우선적으로는, 주어진 words 배열을 돌며 하나의 문자열을 만들 수 있는 단어의 집합을 만들어야 한다. 기본적으로 단어들이 가지는 최소 문자열의 길이는, 각 단어의 길이 + 단어 사이 최소한 공백(" ")이기 때문에 이를 바탕으로 maxWidth를 넘는지를 판단해 단어들을 추가해나간다. 그러다가 더 이상의 단어 추가가 불가능하다면, 이 때까지의 단어 집합을 바탕으로 문자열 생성을 해나간다.
 우선 단어 집합 속 단어가 한 개라면, maxWidth 중 해당 단어 길이를 제외한 나머지를 모두 단어 옆에 공백으로 추가하면 된다. 그 외의 경우엔 공백 길이의 계산이 필요한데, 우선 단어들 사이에 공백의 길이가 고르게 퍼져야 하기 때문에 기본적인 공백의 크기를 계산하고, 그 외에도 남는 공백의 길이를 계산한다. 이후 단어 사이 공백을 넣는 과정에서, 만약 기본적인 공백의 크기 외에 남는 공백이 존재한다면 기본 공백 크기+1의 길이로 공백을 넣어주고 단어를 append하고, 남는 공백이 없다면 단순 기본 공백 크기만큼의 공백을 넣어주고 단어를 append 한다. 이후 결과 StringBuilder를 문자열로 반환해주면 된다.
 앞선 과정을 통해 단어들의 집합을 만들어내고, 집합을 바탕으로 문자열을 생성해나가는 경우 마지막에는 최종 단어들의 집합이 남게 된다. 다만 이 경우엔 일반적인 문자열 생성이 아닌 특별한 조건으로 문자열 생성을 해줘야 하는데, 마지막 줄의 라인인 만큼 공백을 고르게 퍼트리는게 아닌, 단순 왼쪽 정렬 형태를 띄어야 한다. 이를 위해 단어 사이의 공백을 길이 1만큼만 넣어주고, 그 외 남은 길이는 마지막에 추가로 붙여줘야 한다. 이후 결과적으로 모든 단어들에 대해 문자열 생성을 완료했다면, 결과 리스트를 반환해주면 된다.

 

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> answer = new LinkedList<>(), candidates = new LinkedList<>();
        int totalWordLength = words[0].length();
        candidates.add(words[0]);

        for (int i = 1; i < words.length; i++) {
            if (totalWordLength + candidates.size() + words[i].length() <= maxWidth) {//단어 추가 가능
                candidates.add(words[i]);
                totalWordLength += words[i].length();
            } else {//더 이상의 단어 추가가 불가능한 경우 
                answer.add(formatting(candidates, totalWordLength, maxWidth));//이전까지의 목록을 바탕으로 문자열 생성

                //새로 초기화
                candidates = new LinkedList<>();
                candidates.add(words[i]);
                totalWordLength = words[i].length();
            }
        }

        //마지막 줄 포맷팅
        StringBuilder formatResult = new StringBuilder(candidates.get(0));

        for (int i = 1; i < candidates.size(); i++) {
            formatResult.append(" ").append(candidates.get(i));
        }

        formatResult.append(" ".repeat(maxWidth - totalWordLength - candidates.size() + 1));
        answer.add(formatResult.toString());

        return answer;
    }

    String formatting(List<String> candidates, int totalWordLength, int maxWidth) {
        StringBuilder formatResult = new StringBuilder(candidates.get(0));

        if (candidates.size() == 1) {//포함 단어가 1개라면
            formatResult.append(" ".repeat(maxWidth - totalWordLength));
        } else {
            int commonSpaceLength = (maxWidth - totalWordLength) / (candidates.size() - 1);//공통적으로 가져야 하는 공백 크기
            int additionalSpace = maxWidth - totalWordLength - (commonSpaceLength * (candidates.size() - 1));//추가적인 나머지 공백

            for (int i = 1; i < candidates.size(); i++) {
                if (additionalSpace != 0) {//추가적인 공백이 있다면 공통 크기 공백+1
                    formatResult.append(" ".repeat(commonSpaceLength + 1)).append(candidates.get(i));
                    --additionalSpace;
                } else {//없다면 공통 크기 공백만
                    formatResult.append(" ".repeat(commonSpaceLength)).append(candidates.get(i));
                }
            }
        }

        return formatResult.toString();//문자열 반환
    }
}

결과