[코딩 인터뷰][Hacker Rank] Abbreviation

※ 이 포스트는 HackerRank 코딩 인터뷰 문제인 Abbreviation 의 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

문제 정보

문제 출처 : Abbreviation (https://www.hackerrank.com/challenges/abbr/problem)
카테고리 : DP
난이도 : 쉬움

---

문제 설명

문자열 A와 B가 주어진다. A에 대해서 다음과 같은 변환을 할 수 있다.
1. A의 어떤 소문자들을 선택해서, 대문자로 바꿀 수 있다.
2. A의 남은 소문자들을 모두 삭제한다.
이 변환으로 A를 B와 동일하게 만들 수 있는지 판별하여라.

예를 들어 A = “AbcDE”이고, B는 “ABDE”인 경우를 살펴본다.
A[1]의 ‘b’를 대문자로 바꾸고 A[2]의 ‘c’를 소문자로 바꾼 결과는 B와 일치한다.

---

문제 풀이

DP를 사용해 문제를 풀이 할 수 있다.
DP[ i ][ j ]는 변환을 통해 A{ : i ]와 B{ : j ]를 일치하게 할 수 있는지에 대한 여부다.
DP[ i ][ j ]는 다음과 같이 점화식을 설정할 수 있다.
1. A[ i ]가 소문자인 경우, D[ i – 1 ][ j ]가 참( A[ : i – 1]과 B[ j ]가 일치 가능하므로 A[ i ]를 삭제한다)이면 D[ i ][ j ]도 참이다.
2. D[ i – 1 ][ j – 1 ]가 참인 경우 A[ i – 1 ]이 B[ j – 1 ]과 같거나 A[ i – 1 ]을 대문자로 바꾸어 B[ j – 1 ]과 같으면 D[ i ][ j ]도 참이다.
이중 Loop를 통해 점화식을 적용한 후에 최종적으로 DP[len(a)][len(b)]가 참이면 YES, 아니면 NO를 출력한다.

---

코드

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the abbreviation function below.
def isEqual(a, b):
    return a == b or a.upper() == b

def abbreviation(a, b):
    DP = []
    for i in range(len(a) + 1):
        DP.append([False] * (len(b) + 1))
    DP[0][0] = True
    
    for i in range(1, len(a) + 1):
        for j in range(0, len(b) + 1):
            if j > 0 and DP[i - 1][j - 1] and isEqual(a[i - 1], b[j - 1]):
                DP[i][j] = True
            if ord(a[i - 1]) >= 97 and DP[i - 1][j]:
                DP[i][j] = True

    return "YES" if DP[len(a)][len(b)] else "NO"

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    for q_itr in range(q):
        a = input()
        b = input()

        result = abbreviation(a, b)

        fptr.write(result + '\n')

    fptr.close()

---

코딩 인터뷰 – Abbreviation