※ 이 포스트는 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
합격왕 우여곡절 끝에 드디어 합격왕에 광고를 붙였다. 서비스를 시작한지 무려 4년이 지나서야 드디어 광고를 시작하게…
반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…
Planning A well-structured plan has the following characteristics: First, the ultimate vision you aim to…
English The most common problem for English learners like myself is that we often use…
This website uses cookies.