There is a strange printer with the following two special properties:
The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.
Given a string s, return the minimum number of turns the printer needed to print it.
Example 1:
Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".
Example 2:
Input: s = "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
Constraints:
1 <= s.length <= 100
s consists of lowercase English letters.
컨텍스트를 이해해보자
The problem is about minimizing the number of times a printer needs to print characters from a string, where the printer can print a contiguous block of the same character.
- 프린터가 문자열에서 문자를 인쇄하는데 필요한 횟수를 최소화하자
- 프린터는 동일한 문자의 연쇄 블록을 인쇄할 수 있음
The key insight is that if the same character appears multiple times in the string,
- 핵심은 동일한 문자가 문자열에 여러번 나타나는 경우
we can leverage this to reduce the number of print operations.
- 이 점(중복 재사용)을 통해 인쇄 작업수 줄이기가 가능해짐
For example, if we have the string "aaabbb", we can first print 'a' three times,
- "aaabbb" -> 우선 "a"를 3번 인쇄 가능
and then print 'b' three times, resulting in two print operations instead of printing each character individually.
- 그런 다음 "b"를 3번 인쇄하면 각 문자를 개별적으로 인쇄하는 대신 두 번의 인쇄 작업이 수행됨
접근
Approach
Dynamic Programming: We will use a 2D array dp where dp[i][j] represents the minimum number of print operations required to print the substring from index i to j.
- 2D 배열 dp를 사용
dp[i][j]는 i에서 j까지 하위 문자열을 인쇄하는데 필요한 최소 인쇄 작업수
Recursive Function: The function Util(i, j) computes the minimum print operations for the substring s[i:j].
- 재귀함수
Util(i, j)는 하위 문자열 s[i:j]에 대한 최소 인쇄 작업을 개선
If i > j, it returns 0 (base case).
If dp[i][j] is already computed (not -1), it returns the stored value.
- i > j이면 0(기본 사례)을 반환
- dp[i][j]가 이미 계산된 경우(-1 아님) 저장된 값을 반환
The first print operation is always counted, and then we check for any repeated characters in the substring to potentially reduce the number of operations.
- 첫번째 인쇄작업은 항상 계산되며
- 잠재작업수를 줄이고자 하위 문자열에서 반복되는 문자가 있는지 확인
Character Matching: For each character in the substring starting from i, if it matches the first character (s[i]), we can consider splitting the problem into two parts: printing from i to k-1 and from k+1 to j.
- 문자일치: i에서 시작되는 하위 문자열의 각 문자에 대해 첫번째 문자(
s[i])와 일치하면 문제를 두 부분으로 분할하는 것을 고려할 수 있습니다 - 즉, i에서 k-1로 인쇄하고 k+1에서 j로 인쇄하는 것
Memoization: Store the results of subproblems in dp to avoid redundant calculations.
- 메모이제이션 : 중복 계산을 피하기 위해 하위 문제의 결과를 dp에 저장
차근차근 이해해보자
For Input "aaabbb"
Let's trace the execution of the code with the input "aaabbb":
- 입력 "aaabbb"의 경우 코드 실행을 추적해보자면
Initialization:
n = 6 (length of "aaabbb").
dp is initialized to a 6x6 matrix filled with -1.
First Call: strangePrinter("aaabbb") calls Util(0, 5).
초기화:
n = 6("aaabbb"의 길이).
- dp는 -1로 채워진 6x6 행렬로 초기화
- 첫 번째 호출: strangerPrinter("aaabbb")는 Util(0, 5)를 호출
Util(0, 5):
firstLetter = 'a'.
Initial answer = 1 + Util(1, 5) (printing 'a' once and considering the rest).
Util(1, 5):
- a를 한번 인쇄하고 나머지를 고려
firstLetter = 'a'.
Initial answer = 1 + Util(2, 5).
Util(2, 5):
firstLetter = 'a'.
Initial answer = 1 + Util(3, 5).
Util(3, 5):
firstLetter = 'b'.
Initial answer = 1 + Util(4, 5).
Util(4, 5):
firstLetter = 'b'.
Initial answer = 1 + Util(5, 5).
Util(5, 5):
firstLetter = 'b'.
Initial answer = 1 + Util(6, 5).
Util(6, 5) returns 0 (base case).
Backtrack to Util(4, 5):
answer = 1 + 1 = 2.
Check for repeated characters:
k = 5: s matches firstLetter ('b').
Calculate betterAnswer = Util(4, 4) + Util(6, 5) = 1 + 0 = 1.
Update answer = min(2, 1) = 1.
Backtrack to Util(3, 5):
answer = 1 + 1 = 2.
Check for repeated characters:
k = 4: s matches firstLetter ('b').
Calculate betterAnswer = Util(3, 3) + Util(5, 5) = 1 + 1 = 2.
Update `answer = min(2, 2) = 2.
Backtrack to Util(2, 5):
answer = 1 + 2 = 3.
Check for repeated characters:
k = 3: s matches firstLetter ('a').
Calculate betterAnswer = Util(2, 2) + Util(4, 5) = 1 + 1 = 2.
Update `answer = min(3, 2) = 2.
Backtrack to Util(1, 5):
answer = 1 + 2 = 3.
Check for repeated characters:
k = 2: s matches firstLetter ('a').
Calculate betterAnswer = Util(1, 1) + Util(3, 5) = 1 + 1 = 2.
Update `answer = min(3, 2) = 2.
Backtrack to Util(0, 5):
answer = 1 + 2 = 3.
Check for repeated characters:
k = 1: s matches firstLetter ('a').
Calculate betterAnswer = Util(0, 0) + Util(2, 5) = 1 + 2 = 3.
Update `answer = min(3, 3) = 3.
Final Result: The final value of dp is 3, which means a minimum of 3 print operations are needed to print "aaabbb".
풀이
class Solution {
public int strangePrinter(String s) {
int n = s.length();
char[] sChar = s.toCharArray();
int[][] dp = new int[n][n];
for(int[] in : dp) Arrays.fill(in, -1);
return Util(0, n - 1, sChar, dp);
}
public int Util(int i, int j, char[] sChar, int[][] dp) {
if (i > j) {
return 0;
}
if(dp[i][j] != -1) return dp[i][j];
int firstLetter = sChar[i];
// in case, current character is not repeated in the rest of the string
int answer = 1 + Util(i + 1, j, sChar, dp);
for (int k = i + 1; k <= j; k++) {
// if repeated then update the answer
if (sChar[k] == firstLetter) {
// splitting from i -> k - 1(remove the last character)
// and from k + 1 -> j
int betterAnswer = Util(i, k - 1, sChar, dp) + Util(k + 1, j, sChar, dp);
answer = Math.min(answer, betterAnswer);
}
}
return dp[i][j] = answer;
}
}