단어 배열과 최대 너비(maxWidth)가 주어지면, 각 줄이 정확히 maxWidth개의 문자를 갖도록 텍스트를 양쪽 정렬(full justify) 형식으로 포맷해야 합니다. 단어는 탐욕(greedy) 방식으로 배치하며, 즉 각 줄에 가능한 한 많은 단어를 담습니다. 필요할 때 여분의 공백(' ')을 채워 넣어 모든 줄의 길이를 정확히 maxWidth로 맞춥니다.
이때 단어 사이의 여분 공백은 최대한 균등하게 분배해야 합니다. 한 줄의 공백 수가 단어 사이에 고르게 나누어 떨어지지 않는 경우에는 왼쪽 빈 슬롯이 오른쪽 슬롯보다 더 많은 공백을 배정받습니다. 마지막 줄은 왼쪽 정렬로 처리하며, 단어 사이에 여분의 공백을 삽입하지 않습니다.
그럼 해결 절차를 단계별로 살펴보겠습니다.
해결 절차
- result라는 이름의 결과 배열을 생성합니다.
- i를 0부터 배열 a의 크기까지 순회하되, 한 줄의 처리가 끝날 때마다 i를 j 값으로 갱신합니다.
- width := 0 으로 초기화합니다.
- j를 i부터 배열 a의 크기까지, 'width + a[j]의 길이 + (j − i) ≤ b' 조건이 성립하는 동안 반복합니다.
- width := width + a[j]의 길이
- space := 1, extra := 0 으로 초기화합니다.
- 'j − i ≠ 1'이고 'j ≠ 배열 a의 크기'인 경우:
- space := (b − width) ÷ (j − i − 1)
- extra := (b − width) mod (j − i − 1)
- line := a[i]
- k를 i + 1부터 j − 1까지 반복합니다.
- line에 space개의 공백을 이어 붙입니다.
- extra > 0이면 공백 하나를 추가로 붙입니다.
- extra 값을 1 감소시킵니다.
- line에 a[k]를 이어 붙입니다.
- x := line의 길이
- line 끝에 (b − x)개의 공백을 덧붙여 길이를 b로 맞춥니다.
- 완성된 line을 result에 삽입합니다.
- result를 반환합니다.
예제 코드
아래 C++ 구현 예시를 통해 동작 과정을 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
void print_vector(vector<vector<auto>> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> fullJustify(vector<string> &a, int b) {
vector <string> result;
int i, j;
for(i = 0; i < a.size(); i = j){
int width = 0;
for(j = i; j < a.size() && width + a[j].size() + j - i <= b; j++){
width += a[j].size();
}
int space = 1;
int extra = 0;
if(j - i != 1 && j != a.size()){
space = (b - width) / (j - i - 1);
extra = (b - width) % (j - i - 1);
}
string line(a[i]);
for(int k = i + 1; k < j; k++){
line += string(space, ' ');
if(extra-- > 0){
line += " ";
}
line += a[k];
}
int x = line.size();
line += string(b - x, ' ');
result.push_back(line);
}
return result;
}
};
main(){
vector<string> v = {"I", "love", "coding.", "here", "we", "will", "write", "some", "program"};
Solution ob;
print_vector(ob.fullJustify(v, 16));
}입력
["I", "love", "coding.", "here", "we", "will", "write", "some", "program"] 16
출력
[I love coding., here we will, write some, program , ]
실행 결과를 보면 첫 번째 줄부터 세 번째 줄까지는 양쪽 정렬 규칙에 따라 공백이 균등하게 분배된 것을 확인할 수 있습니다. 반면 마지막 줄의 'program'은 남은 단어가 없으므로 왼쪽 정렬된 상태로 처리되고, 부족한 길이만큼 오른쪽이 공백으로 채워집니다. 이 알고리즘은 각 단어를 한 번씩만 검사하므로 전체 시간 복잡도는 단어 수에 비례하는 O(N)입니다.