[HackerRank] Abbreviation 풀이 Java

Abbreviation | HackerRank

 

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