C++ 문장 화면 맞춤 알고리즘 구현 방법

rows × cols 크기의 화면과 비어 있지 않은 단어들로 구성된 문장이 주어졌을 때, 이 문장 전체가 화면에 몇 번 온전히 들어갈 수 있는지 구하는 문제입니다. 이 문제에는 다음과 같은 제약 조건이 있습니다.

단어는 두 줄에 걸쳐 나뉘어질 수 없습니다.
문장 안에서 단어의 순서는 절대 바뀌지 않습니다.
두 단어 사이에는 공백이 정확히 하나만 존재합니다.
문장을 이루는 단어의 총 개수는 100개를 초과하지 않습니다.
각 단어의 길이는 0보다 크고 10보다 작습니다.
1 ≤ rows, cols ≤ 20,000 입니다.

예를 들어 rows = 3, cols = 6이고 문장이 ["a", "bcd", "e"]라고 가정해 보겠습니다. 첫 줄에는 "a bcd"(5자)가 배치되고, 둘째 줄에는 "e a"(3자), 셋째 줄에는 "bcd e"(5자)가 들어갑니다. 이렇게 총 6개의 단어가 화면에 놓이므로, 3개 단어로 이루어진 문장 기준으로 2번 완전히 반복된 셈입니다. 따라서 출력값은 2가 됩니다.

알고리즘 접근 방법

이 문제는 메모이제이션(캐싱)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 행의 시작 위치, 즉 시작 단어의 인덱스가 같다면 그 행에 놓일 수 있는 단어 수도 항상 동일하다는 점입니다. 해결 단계는 다음과 같습니다.

맵 dp를 정의하고, ret := 0, n := 문장 배열의 크기로 초기화합니다.
row가 0이 아닌 동안 다음 과정을 반복합니다.
- start := ret mod n, len := -1, cnt := 0으로 설정합니다.
- start가 dp에 없는 경우:
  - 1 + len + sentence[(start + cnt) mod n]의 길이가 cols 이하인 동안 반복합니다.
    - len := 1 + len + sentence[(start + cnt) mod n]
    - cnt를 1 증가시킵니다.
  - dp[start] := cnt로 저장합니다.
  - ret := ret + cnt로 갱신합니다.
- 그렇지 않은 경우, 이미 계산된 값을 재사용하여 ret := ret + dp[start]로 갱신합니다.
- row := row − 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