Java, LeetCode | 418. Sentence Screen Fitting

🚀 풀이 후기

DP.. 너무 어렵습니다.

string에서 index와 size가 1이 차이나다 보니 더 헷갈립니다. 

🌒 문제 설명

주어진 sentence 문자열 배열이 rows * cols 의 스크린에 몇 번 채워질 수 있는지 반환하는 문제입니다.

문자열 배열의 순서는 바꿀 수 없고, 각 문자는 2줄로 쪼개져서도 안됩니다.

같은 줄에서 각각의 문자는 구분되어야 합니다.

Given a rows x cols screen and a sentence represented as a list of strings, 
return the number of times the given sentence can be fitted on the screen.

The order of words in the sentence must remain unchanged, 
and a word cannot be split into two lines. 
A single space must separate two consecutive words in a line.

 

Example 1:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1
Explanation:
hello---
world---
The character '-' signifies an empty space on the screen.


Example 2:

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.


Example 3:

Input: sentence = ["i","had","apple","pie"], rows = 4, cols = 5
Output: 1
Explanation:
i-had
apple
pie-i
had--
The character '-' signifies an empty space on the screen.
 

Constraints:

1 <= sentence.length <= 100
1 <= sentence[i].length <= 10
sentence[i] consists of lowercase English letters.
1 <= rows, cols <= 2 * 104

🌓 문제 풀이

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String combined = String.join("-", sentence) + "-"; // 문자 배열을 한 줄로 만듭니다. ex) hello_world_ 
        int start = 0; // row 에서 문자가 시작할 수 있는 index입니다.
        while (rows-- > 0) { // rows만큼 순환합니다.
            start += cols;  // row가 끝나는 index로 갑니다.
            
            // row의 맨 뒤 index에 해당하는 문자가 '-'인지 확인합니다.
            if (combined.charAt(start % combined.length()) == '-') { 
                start++; // 다음 row에서 시작하는 index를 찾아갑니다.
            } else {
                // row 맨 뒤 index에 해당하는 문자가 '-' 가 될 때까지 start-- 합니다.
                while (start > 0 && combined.charAt((start - 1) % combined.length()) != '-') {
                    start--;
                }
            }
        }
        
        // rows를 순환하며 길어진 start를 최초 문자열인 combined의 길이로 나눈 몫이 반복 횟수가 됩니다.
        return start / combined.length(); 
    }
}

 

- 시간복잡도: O(N)

N = rows, 1 <= rows <= 2*10^4

- 공간복잡도: O(1)

---

리트코드 문제

깃허브 코드