Leetcode - 418. Sentence Screen Fitting

문제

문장과 스크린 사이즈가 주어진다. 해당 문장을 스크린에 몇번 담을 수 있는지 파악하라.

Input: sentence = ["a", "bcd", "e"], rows = 3, cols = 6
Output: 2
Explanation:
a-bcd- 
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.

해결

discussion을 참고했다. 배열 인덱싱이 많고, 코드 복잡도가 높아서 어려운 문제였다.

• 아이디어

  • 해시테이블 키: 문자 인덱스, 값: 해당 문자로 시작할때 한 라인에 채워지는 단어갯수
  • rows를 순회하면서 각 라인을 시작하는 첫 문자 idx를 구하고, 해당 idx에 해당하는 해시테이블값을 구하고 누적해서 더한다
  • 그 더한 값을 총 문자갯수로 나누면 전체스크린이 몇개필요한지 구할 수 있음.

• unordered_map 배운것

  • table.count(key) 로 key가 해시테이블에 존재하는지 체크 가능. unordered_map은 중복을 허용하지 않기 때문에, 0인지 아닌지로 키값존재 유무 체크가능.

class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        unordered_map<int, int> table; 
        // key: idx of sentence 
        // value: how many word in a line
        
        int idx = 0;
        int ssize = sentence.size();
        int num = 0;
        
        for (int i = 0; i < rows; i++) {
            idx = num % ssize;
            if (table.count(idx) == 0) {
                // if new, calculate number of words in a line from begin with sentence[idx]
                int cnt = 0, len = 0;
                int j = idx;
                while (len < cols) {
                    j = (j + 1) % ssize;
                    if (len + sentence[j].size() > cols)
                        break;
                    len += sentence[j].size() + 1;
                    cnt++;
                }
                num += cnt;
                table[idx] = cnt;
            } else {
                // if exist, just return from hashtable
                num += table[idx];
            }
        }
        return num / ssize;
    }
};

해결 brute force -> (TLE)

brute force 방법. 아래 예제에서 TLE발생. (34 / 51 test cases passed)

["a","b"]
20000
20000

class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int tot_screen = 0;
        int idx = 0;
        int nr_sent = sentence.size();
        int remein_col = cols;
        int cur_row = 0;
        int cur_s_len = 0;
        int *len_arr = new int[nr_sent];
        
        for (int i = 0; i < nr_sent; i++)
            len_arr[i] = sentence[i].size();
        while (cur_row < rows) {
            cur_s_len = len_arr[idx];
                
            if (cur_s_len <= remein_col) { /* fit in cur row */
                if (cur_s_len == remein_col)
                    remein_col -= cur_s_len;
                else
                    remein_col -= (cur_s_len + 1);
                idx++;
                if (idx >= nr_sent) {
                    idx = 0;
                    tot_screen++;
                }
            } else { /* doesn't fit in cur row */
                remein_col = cols;
                cur_row++;
            }
        }
        return tot_screen;
    }
};