C++의 문장 화면 맞춤

<시간/>

행 x 열 화면과 비어 있지 않은 단어 목록으로 표현되는 문장이 있다고 가정하고 주어진 문장을 화면에 몇 번이나 맞출 수 있는지 찾아야 합니다. 특정 속성이 있습니다 -

단어는 두 줄로 나뉘지 않습니다.
문장에서 단어의 순서는 변경되지 않아야 합니다.
두 단어 사이에는 공백이 하나만 있어야 합니다.
문장의 총 단어 수는 100을 초과하지 않습니다.
각 단어의 길이는 0보다 크고 10보다 작습니다.
1 ≤ 행, 열 ≤ 20,000.

따라서 입력이 행 =3 및 열 =6이고 문장이 ["a", "bcd", "e"]인 경우 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

맵 dp 정의, ret :=0, n :=문장 배열 크기 설정
행이 0이 아닌 동안
- 시작 :=ret mod n, len :=-l 및 cnt :=0
- 시작이 dp에 없으면
  - while 1 + len + 문장 크기[(start + cnt) mod n] <=cols
    - len :=1 + len + 문장[(시작 + cnt) 모드 n]
    - cnt 1 증가
  - dp[시작] :=cnt
  - 렛 :=렛 + cnt
- 그렇지 않으면 ret :=ret + dp[시작]
- 행 :=행 – 1
ret/n을 반환

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int wordsTyping(vector<string>& sentence, int rows, int cols) {
      unordered_map <int, int> dp;
      int ret = 0;
      int n = sentence.size();
      while(rows--){
         int start = ret % n;
         int len = -1;
         int cnt = 0;
         if(!dp.count(start)){
            while(1 + len + (int)sentence[(start + cnt) % n].size() <= cols){
               len = 1 + len + sentence[(start + cnt) % n].size();
               cnt++;
            }
            dp[start] = cnt;
            ret += cnt;
         }
         else{
            ret += dp[start];
         }
      }
      return ret / n;
   }
};
main(){
   vector<string> v = {"a","bcd","e"};
   Solution ob;
   cout << (ob.wordsTyping(v, 3, 6));
}

입력

["a","bcd","e"]
3
6