68. Text Justification - Streak 21

로직 자체는 단순했지만, 구현이 까다로웠던 문제였다.

---

일단 단순하게 접근해보자.

그리디하게 문자열을 넣는다면, 다음 두 단계로 분리해서 실행해야 한다.

1. maxWidth 를 넘지 않는 수준까지 단어를 밀어넣는다.
   • maxWidth를 넘는다면, 다음 줄로 넘겨 넣는다.
2. 각 줄에 대하여, 단어 사이에 순서대로 빈칸을 하나씩 추가한다.

• 마지막 줄의 경우, left-justified 되어야 한다.

이렇게 되면 공백으로 채워야 하는 빈칸의 수는 정해져 있다.
이제 이를 각 단어 사이에 분배하면 된다.

 

 

"마지막 줄로 넘어갈 때 발생하는 예외 케이스는 없을까?" 라는 고민도 있을 수 있는데,
현재 줄의 단어 구성은 이전 줄에 단어를 어떻게 넣었느냐에 따라 달라지기 때문에, 마지막 줄의 left-justified가 이전 줄에 영향을 끼칠 가능성은 없다.

 

 

시간복잡도는 어떻게 될까?
먼저 단어 전체를 순회해야 하니 words.length 만큼의 시간이 걸릴 것이다.
그리고 각 줄 별로 문자열의 길이를 전부 파악하고 있어야 하기 때문에 words.length 만큼의 시간이 걸릴 것이다.

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int n = words.length;
        int now = 0;
        List<List<String>> repo = new ArrayList<>();
        List<String> nowList = new ArrayList<>();
        repo.add(nowList);
        for(String word : words){
            if(now + word.length() + nowList.size() > maxWidth){
                nowList = new ArrayList<>();
                repo.add(nowList);
                now = 0;
            }
            now += word.length();
            nowList.add(word);
        }
        List<String> ret = new ArrayList<>();
        for(int index = 0; index < repo.size(); index++){
            List<String> list = repo.get(index);

            if(index == repo.size() - 1){
                StringBuilder sb = new StringBuilder();
                int cnt = 0;
                for(int i = 0; i<list.size(); i++){
                    sb.append(list.get(i));
                    cnt += list.get(i).length();
                    if(i == list.size() - 1){
                        while(cnt < maxWidth){
                            sb.append(" ");
                            cnt++;
                        }
                    } else {
                        sb.append(" ");
                        cnt += 1;
                    }
                }
                ret.add(sb.toString());
                continue;
            }

            if(list.size() == 1){
                StringBuilder sb = new StringBuilder();
                String word = list.get(0);
                sb.append(word);
                for(int i = 0; i < maxWidth - word.length(); i++) sb.append(" ");
                ret.add(sb.toString());
                continue;
            }

            int wordLength = 0;
            for(String word : list){
                wordLength += word.length();
            }
            int blank = (maxWidth - wordLength) / (list.size() - 1);
            int plusIndex = (maxWidth - wordLength) % (list.size() - 1);

            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < list.size(); i++){
                sb.append(list.get(i));
                if(i == list.size() - 1) continue;
                for(int j = 0; j<blank; j++) sb.append(" ");
                if(i < plusIndex) sb.append(" ");
            }
            ret.add(sb.toString());
        }
        return ret;
    }
}