코테 출제회사: Google, LinkedIn


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




string addSpaces(int cnt){
    return std::string(cnt, ' '); // char
}

// Greedily try to go as far right as possible until we fill our current line
pair<int,int> findRight(vector<string>& words, int maxWidth, int l){
    int wLen = words[l].size(); // sum of lengths of words from l to r. + default whitespaces
    int n = words.size(), r = l+1;
   
    while(r < n && wLen + 1+words[r].size() <= maxWidth){
        wLen += 1+words[r].size(); // +1 for default whitespace
        r++;
    }
    return {r-1, wLen};
}

string makeLine( vector<string>& words, int maxWidth, int l, int r, int wLen){
    int n = words.size(), spaces = maxWidth-wLen; // EXTRA whitespaces needed
   
    if(l == r) return words[l] + addSpaces(spaces);
   
    string line = "";
    bool isLast = (r == n-1);
   
    // Split EXTRA spaces. In between r-l+1 words, there are r-l spaces
    auto [q, rem] = std::div(spaces, r-l);
   
    for(int i=l; i< r; i++){
        line += words[i];
        line += " ";
       
        if(!isLast){
            line += addSpaces(q);
            if(rem > 0) line += " ";  // evenly distribute remaining spaces
            rem--;
        }
    }
    line += words[r];
    if(isLast) line += addSpaces(spaces); // left justify
   
    return line;
}

vector<string> Solution::fullJustify( vector<string>& words, int maxWidth) {
    int n = words.size(), l=0, r=0;
    vector<string> ans;
   
    while(l < n){
        auto [r, wLen] = findRight( words, maxWidth, l);
        string line = makeLine( words, maxWidth, l, r, wLen);
        ans.push_back( line);
        l = r+1;
    }
    return ans;
}