문제 소개
단어 목록과 고정 너비 k가 주어졌을 때, 각 줄이 정확히 k개의 문자를 포함하도록 텍스트를 배치하고 완전히 양쪽 정렬(full justify)된 결과를 만들어야 합니다. 한 줄에는 들어갈 수 있는 만큼 최대한 많은 단어를 담고, 남는 자리는 추가 공백(' ')으로 채워 모든 줄의 길이를 k자로 맞춥니다.
단어 사이의 여분 공백은 최대한 균등하게 분배해야 합니다. 공백 수를 단어 사이에 균등하게 나눌 수 없는 경우에는 왼쪽 빈 슬롯이 오른쪽 슬롯보다 더 많은 공백을 할당받습니다. 마지막 줄은 왼쪽 정렬을 하며, 단어 사이에 여분의 공백을 삽입하지 않습니다.
입력·출력 예시
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
["The", "grumpy", "wizards", "make", "toxic", "brew", "for", "the", "evil", "queen", "and", "Jack"], k = 13
그러면 출력은 아래와 같습니다.
The grumpy wizards make toxic brew for the evil queen and Jack
실제 결과에서는 각 줄의 뒤에 공백이 채워져 길이가 정확히 13자가 됩니다.
풀이 접근 방법
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 한 줄에 최대한 많은 단어를 담은 뒤, 남은 공간을 규칙에 따라 공백으로 분배하는 것입니다. 구체적인 단계는 다음과 같습니다.
- 결과를 저장할 배열 result를 생성합니다.
- i를 0부터 배열 a의 크기까지 순회하되, 한 줄 처리가 끝날 때마다 i를 j 값으로 갱신합니다.
- width를 0으로 초기화한 뒤, j를 i부터 탐색하며 'width + a[j]의 길이 + (j − i) ≤ b' 조건을 만족하는 동안 width에 단어 길이를 누적합니다. 이렇게 한 줄에 들어갈 단어의 범위를 결정합니다.
- space는 1, extra는 0으로 초기화합니다.
- 현재 줄이 마지막 줄이 아니고(j ≠ 배열 크기), 줄에 단어가 두 개 이상 있으면(j − i ≠ 1) 다음을 계산합니다.
- 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를 감소시킵니다. 그다음 단어 a[k]를 line에 연결합니다.
- line의 현재 길이를 x라 할 때, 부족한 길이(b − x)만큼 공백을 뒤에 덧붙여 정확히 b자로 만듭니다.
- 완성된 line을 result에 삽입합니다.
- 모든 단어를 처리한 후 result를 반환합니다.
핵심 아이디어는 extra 값을 활용해 왼쪽 슬롯부터 공백을 하나씩 추가로 배분함으로써, "왼쪽이 오른쪽보다 많은 공백을 갖는다"는 조건을 자연스럽게 만족시킨다는 점입니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i] << ", ";
}
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 = {"The", "grumpy", "wizards", "make", "toxic", "brew", "for", "the", "evil", "queen", "and", "Jack"};
Solution ob;
print_vector(ob.fullJustify(v, 13));
}
실행 결과
위 코드를 컴파일하여 실행하면 다음과 같은 출력을 얻습니다.
[The grumpy, wizards make, toxic brew, for the evil, queen and, Jack ]
출력상 각 행의 끝에는 실제로 공백 문자가 채워져 있으며, 따라서 모든 줄의 길이가 정확히 13자로 일치합니다.
복잡도 분석
시간 복잡도는 전체 문자 수에 비례하는 O(N)이며, 공간 복잡도 역시 결과를 저장하는 데 필요한 O(N)입니다. 각 단어가 정확히 한 번씩만 방문되므로 매우 효율적인 알고리즘이라고 할 수 있습니다.