68. Text Justification

LeetCode 갤러리
마이너

자동 짤방 이미지

이미지가 없습니다.

자동 짤방으로 사용할 이미지를 등록해 주세요.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

ㅇㅇ(12.50) 2023.01.08 06:20:16

조회 34 추천 0 댓글 0

코테 출제회사: 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;
}

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
86	909. Snakes and Ladders [1]	개발뉴비	23.01.24	54	0
85	909. Snakes and Ladders	이벤트ㅇㅅㅇ(219.251)	23.01.24	47	0
83	997. Find the Town Judge	이벤트ㅇㅅㅇ(219.251)	23.01.23	44	0
82	997. Find the Town Judge [1]	개발뉴비	23.01.23	74	0
81	백준 9996번	키비	23.01.23	56	0
78	마갤 입문함 [2]	키비	23.01.22	59	0
77	131. Palindrome Partitioning [1]	개발뉴비	23.01.22	57	0
75	93. Restore IP Addresses [1]	개발뉴비	23.01.21	72	0
74	Longest Palindromic Substring 5번	o오어o(14.37)	23.01.21	30	0
73	Restore IP Addresses 93번	o오어o(14.37)	23.01.21	38	0
72	안녕하세요 오늘부터 릿코 달리게씁니당 [2]	조르디(112.170)	23.01.21	53	0
71	491. Non-decreasing Subsequences [1]	개발뉴비	23.01.21	56	0
70	974. Subarray Sums Divisible by K [1]	개발뉴비	23.01.19	43	0
69	926. Flip String to Monotone Increasing [1]	개발뉴비	23.01.17	40	0
68	57. Insert Interval [1]	개발뉴비	23.01.17	37	0
66	트리 문제 두 개 개빡치네;	개발뉴비	23.01.15	47	0
65	1061. Lexicographically Smallest ~	개발뉴비	23.01.15	40	0
64	여기 갤럼들은 전부 해외취업 준비중? [2]	EvenAsura	23.01.14	105	0
63	1519. Number of Nodes in the Sub-Tree~	개발뉴비	23.01.12	28	0
62	1443. Minimum Time to Collect All Apples	개발뉴비	23.01.11	40	0
59	230111 데일리	꽃지	23.01.11	68	0
58	100. Same Tree	개발뉴비	23.01.10	34	0
56	220110 데일리	꽃지	23.01.10	40	0
53	144. Binary Tree Preorder Traversal	개발뉴비	23.01.09	40	0
52	230109 데일리	꽃지	23.01.09	31	0
51	리트코드 4번 [4]	o오어o(222.121)	23.01.09	65	0
50	리트코드 3번	o오어o(222.121)	23.01.09	25	0
49	220108 데일리	꽃지	23.01.08	54	0
	68. Text Justification	ㅇㅇ(12.50)	23.01.08	34	0
47	3번문제 코드 딱 한줄만 알려준다	ㅇㅇ(218.234)	23.01.08	37	0
46	코딩 테스트 tdd로 하시는 분 [1]	TS(119.64)	23.01.07	61	0
45	가스스테이션(데일리)	o오어o(222.121)	23.01.07	51	0
44	230107 데일리 [1]	꽃지	23.01.07	55	0
43	134. Gas Station	개발뉴비	23.01.07	47	0
42	1833. Maximum Ice Cream Bars	개발뉴비	23.01.06	58	0
41	230106 데일리	꽃지	23.01.06	50	0
38	오늘의 릿코드 Minimum Number of Arrows~	개발뉴비	23.01.05	40	0
36	230105 데일리 [3]	꽃지	23.01.05	65	0
35	2244. Minimum Rounds 이거 푸는데	TS(119.64)	23.01.05	36	0
34	데일리 문제 어떻게 알아봄...? [1]	TS(119.64)	23.01.05	40	0
33	230104 데일리 [2]	꽃지	23.01.04	86	0
31	Minimum Rounds to Complete All Task [1]	개발뉴비	23.01.04	102	0
30	944. Delete Columns to Make Sorted in TS	ㅇㅇ(119.64)	23.01.04	43	0
29	백준 17726 Inheritance	꽃지	23.01.04	57	0
28	백준 14503번 로봇 청소기	개발뉴비	23.01.04	93	0
23	오늘의 릿코드 Delete Columns to Make Sorted [2]	개발뉴비	23.01.03	78	0
22	오늘의 데일리 [3]	꽃지	23.01.03	83	0
19	리트코드 해보면서 느낀 점	ㅇㅇ(119.64)	23.01.03	90	0
18	어쨌든 TS로 대문자 판별하기 문제 풀었는데	ㅇㅇ(119.64)	23.01.03	47	0
17	저는 js로 할게요 [5]	ㅇㅇ(119.64)	23.01.03	80	0