SWEA 13240. 정사각형 글꼴

세로 H, 가로 W인 격자에 같은 크기의 정사각형의 크기로 단어들을 공백으로 구분하여 넣을 때 단어가 끊기지 않고 전부 넣어질 수 있는 글자의 크기의 최댓값을 구하는 문제이다.

 

글자의 크기를 가로와 세로의 최솟값값까지 넣을 수 있는 경우의 수가 있으므로 1과 가로와 세로의 최솟값 사이에 있는 글자의 크기를 찾는다. 이를 위해 이진 탐색으로 길이를 변경하면서 가능한 길이를 찾는다. 해당 길이의 가능 여부는 해당 길이로 만들 수 있는 한 줄의 최대 글자 수, 최대 줄의 수를 구한 다음 단어들을 배치하여 모든 단어를 배치할 수 있다면 가능하고 단어의 길이가 한 줄의 최대 글자수 보다 크거나 칸이 모자르다면 불가능하다.

private static boolean isPossible(int mid, int h, int w, String[] board) {
    int maxLines = h / mid;
    int maxCols = w / mid;
        
    if (maxLines == 0 || maxCols == 0) return false;
        
    int linesUsed = 1;
    int currentLineWidth = 0;
        
    for (String word : board) {
        int len = word.length();
        if (len > maxCols) return false;
            
        if (currentLineWidth == 0) {
            currentLineWidth = len;
        } else {
            if (currentLineWidth + 1 + len <= maxCols) {
                currentLineWidth += 1 + len;
            } else {
                linesUsed++;
                currentLineWidth = len;
            }
        }
        if (linesUsed > maxLines) return false;
    }
        
    return linesUsed <= maxLines;
}

int l = 1, r = Math.min(h, w);
int max = 0;
            
while (r >= l) {
    int mid = l + (r - l) / 2;
                
    if (isPossible(mid, h, w, board)) {
        max = mid;
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}
sb.append(max).append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for(int tc=1; tc<=T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            
            String[] board = new String[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) {
                board[i] = st.nextToken();
            }
            
            
            int l = 1, r = Math.min(h, w);
            int max = 0;
            
            while (r >= l) {
                int mid = l + (r - l) / 2;
                
                if (isPossible(mid, h, w, board)) {
                    max = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            sb.append(max).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static boolean isPossible(int mid, int h, int w, String[] board) {
        int maxLines = h / mid;
        int maxCols = w / mid;
        
        if (maxLines == 0 || maxCols == 0) return false;
        
        int linesUsed = 1;
        int currentLineWidth = 0;
        
        for (String word : board) {
            int len = word.length();
            if (len > maxCols) return false;
            
            if (currentLineWidth == 0) {
                currentLineWidth = len;
            } else {
                if (currentLineWidth + 1 + len <= maxCols) {
                    currentLineWidth += 1 + len;
                } else {
                    linesUsed++;
                    currentLineWidth = len;
                }
            }
            if (linesUsed > maxLines) return false;
        }
        
        return linesUsed <= maxLines;
    }
}