[LeetCode # 68] Text Justification

주어진 문제는 위 그림과 같다. 문자열을 원소로 갖는 배열 words 와 문장의 최대 폭을 의미하는 maxWidth 값이 주어졌을 때, 주어진 words 를 문장의 형태로 포맷팅하는 것. 

 

우선, 각 문장에 words 의 각 단어들을 그리디하게 패킹한 뒤, 남는 빈 공간들은 공백 문자로 채우는 것이 목표이다. 문제의 해결을 위해 각 단어들마다 한 문장에 포함될 수 있는 지 여부를 확인했다. 단계 별로 문장에 단어가 포함될 수 있는 경우 문장에 단어를 포함시킨 뒤 다음 단어를 탐색하고, 포함될 수 없는 경우 (현재 단어를 문장에 추가할 경우, 단어 사이의 공백이 한 문자 이상 들어갈 수 없을 때 포함될 수 없다고 판단한다.) 현재 문장을 주어진 포맷에 맞게 수정한 뒤 저장하고 새로운 문장에 단어를 추가하는 방식으로 문제를 해결한다.

 

문제의 조건으로, 마지막 문장의 경우는 단어의 개수에 상관 없이 좌측 정렬 (단어 사이의 공백은 한 개로 지정한 뒤, 문장의 뒤에 남는 공간을 모두 공백으로 채움) 하고, 문장에 하나의 단어만 존재하는 경우에도 좌측 정렬을 하도록 되어 있다.

 

위의 문제 해결 방법을 적용한 소스 코드는 다음과 같다.

 

class Solution {
public:
    vector<string> ans;

    string makeSentence(vector<string>& words, int maxWidth, bool option) {
        if (words.size() == 1 || option) {
            string sentence = "";
            for (int i = 0; i < words.size(); i++) {
                sentence += words[i];
                if (i != words.size() - 1) {
                    sentence += " ";
                }
            }
            while (sentence.length() < maxWidth) {
                sentence += " ";
            }
            return sentence;
        }
        
        int len = 0;
        for (auto word : words) {
            len += word.length();
        }

        int blankSpace = maxWidth - len;
        int eachBlank = blankSpace / (words.size() - 1);
        int leftBlank = blankSpace % (words.size() - 1);

        string sentence = "";
        for (int i = 0; i < words.size(); i++) {
            sentence += words[i];
            if (i == words.size() - 1)
                break;
            for (int k = 0; k < eachBlank; k++) {
                sentence += " ";
            }
            if (leftBlank) {
                sentence += " ";
                leftBlank--;
            }
        }

        return sentence;
    }

    void justify(vector<string>& curWords, int totalLength, vector<string>& words, int idx, int maxWidth) {
        if (idx == words.size()) {
            if (!curWords.empty()) {
                ans.push_back(makeSentence(curWords, maxWidth, true));
            }
            return;
        }

        if (totalLength + curWords.size() + words[idx].size() > maxWidth) {
            ans.push_back(makeSentence(curWords, maxWidth, false));
            curWords.clear();
            totalLength = 0;
        }

        curWords.push_back(words[idx]);

        justify(curWords, totalLength + words[idx].length(), words, idx + 1, maxWidth);
    }

    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> curWords;
        justify(curWords, 0, words, 0, maxWidth);

        return ans;
    }
};

소스 코드는 다른 문제들에 비해 길게 작성되었지만, 전체적인 구조는 위에서 설명한 바와 같다.

 

* makeSentence 로직 작성 시, Option 을 추가적으로 받도록 해 마지막 문장인 경우 문제의 추가 조건을 만족시킬 수 있도록 구현했다.