문제 링크
문제 요약
주어진 DNA 가닥 s와 찾으려는 유전자 t가 있습니다.
DNA는 두 가닥으로 이루어져 있으며, 서로 상보적이고 방향이 반대입니다. 염기는 아데닌(A)-티민(T), 구아닌(G)-사이토신(C)이 서로 상보적 관계를 이룹니다.
미샤는 자신의 DNA 중 한 가닥(s)만 받았는데, 이 가닥 또는 다른 상보적인 가닥에 유전자 t가 부분 문자열로 존재하는지 확인해야 합니다.
풀이
이 문제는 문자열 탐색을 수행하는 문제입니다. 주어진 DNA 가닥 s에 특정 유전자 t가 존재하는지 확인하는 간단한 문제이지만, DNA가 두 가닥으로 이루어져 있다는 점을 주의해야 합니다.
미샤는 자신의 DNA 중 한 가닥(s)만을 알고 있지만, 유전자 t는 나머지 한 가닥에도 존재할 수 있습니다.
따라서 풀이는 다음 두 가지 경우를 고려해야 합니다:
-
주어진 가닥
s에 유전자t가 부분 문자열로 존재하는지 확인합니다. 파이썬의in연산자를 사용하여t in s와 같이 간단하게 확인할 수 있습니다. -
s의 상보적인 가닥에 유전자t가 부분 문자열로 존재하는지 확인합니다. DNA의 상보적 관계는 A↔T, C↔G입니다. 또한, 두 가닥은 서로 반대 방향으로 연결되어 있습니다. 이는 한 가닥의역상보(reverse complement)가 다른 가닥이 된다는 의미입니다. 예를 들어,AGC의 상보적인 염기는T C G가 되며, 이를 뒤집으면G C T가 됩니다. (문제 설명의 예시와 일치)따라서
s의 역상보 가닥을 생성해야 합니다.- 먼저
s의 각 염기를 상보적인 염기로 변환합니다. (A→T, T→A, C→G, G→C) - 그다음, 변환된 문자열을 뒤집습니다.
- 이 새로운 역상보 가닥에 유전자
t가 부분 문자열로 존재하는지 다시in연산자로 확인합니다.
- 먼저
두 경우 중 하나라도 t가 존재하면 “Yes”를 출력하고, 그렇지 않으면 “No”를 출력합니다.
문자열 s의 길이는 최대 200, t의 길이는 최대 20이므로, 문자열 연산 및 탐색은 시간 복잡도 면에서 문제가 되지 않습니다.
정답 코드
def reverse(s):
ret = ""
d = {'A': 'T', 'T': 'A', 'C': 'G', 'G': 'C'}
for c in s:
ret += d[c]
return ret[::-1]
def solve():
a = input()
b = input()
if b in a:
print("Yes")
return
a = reverse(a)
if b in a:
print("Yes")
return
print("No")
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()