반응형
DP 문제
a : daBcd
b : ABC
a는 소문자를 대문자로 변경하거나, 모든 소문자를 삭제하는 두 가지 액션을 할 수 있다.
그 결과 a == b 가 될 수 있는지 확인.
참고
처음엔 간단하게 두 문자를 비교하려고 했다.
a의 처음부터 시작해서 소문자면 한칸 뒤로가고 대문자이면서 b와 같으면 b의 인덱스를 증가시키는 방법으로 했는데
16문제 중 4문제가 실패했고 이유를 찾아보니..
<반례>
KeEdC
KEC
이런 케이스 때문에 한 칸씩 뒤로 가면서 확인하는 방법은 쓰면 안됨 XX
유사한 문제 나오면.. 이차원 배열 사용하는 dp 떠올리는게 좋음
코드
i 가 b(ABC) j가 a(daBcd) 를 나타냄
첫번째 for문은 dp[0] 라인에 0번부터 소문자인 true로 설정하며 대문자가 나오면 멈춘다.
d | a | B | c | d | ||
T | T | T | ||||
A | F | T | F | F | F | |
B | F | F | T | T | T | |
C | F | F | F | T | T |
public static String abbreviation(String a, String b) {
boolean[][] dp = new boolean[b.length() + 1][a.length() + 1];
dp[0][0] = true;
for (int j = 1; j < dp[0].length; j++) {
if (Character.isLowerCase(a.charAt(j - 1)))
dp[0][j] = true;
else
break;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
char ca = a.charAt(j - 1);
char cb = b.charAt(i - 1);
// upper
if (ca <= 90) {
if (ca == cb)
dp[i][j] = dp[i - 1][j - 1];
} else {
ca = Character.toUpperCase(ca);
if (ca == cb)
dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1];
else
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[b.length()][a.length()] ? "YES" : "NO";
}
References
https://www.hackerrank.com/challenges/abbr/forum
반응형
'알고리즘' 카테고리의 다른 글
[백준] 2579 계단 오르기 풀이 Java (0) | 2022.07.14 |
---|---|
[백준] 11726 2×n 타일링 풀이 Java (0) | 2022.07.13 |
Alternating Characters 풀이 Java (0) | 2022.07.11 |
Recursion: Davis' Staircase 풀이 Java (0) | 2022.07.10 |
Strings: Making Anagrams java 풀이 (0) | 2022.07.09 |
댓글