[🥉2 / 백준 1672 / 파이썬] DNA 해독

 

1672번: DNA 해독

 

문제

N개의 A, G, C, T로 구성되어 있는 DNA 염기서열이 있다. 그리고 우리는 이 염기서열을 아래의 표를 이용하여 해독을 해야 한다.

 

해독 방법은 염기 서열에서 제일 끝에 있는 두 개의 염기를 An-1, An이라 할 때, An-1을 행으로 An을 열로 대응시켜 그에 해당하는 하나의 염기로 바꾸는 방식을 반복하는 것이다.  예를 들어 AAGTCG라는 염기서열이 있다고 하자. 이 서열을 위의 규칙 때로 해독하면 AAGTCG → AAGTT → AAGT → AAA → AA → A 가 되어 최종적으로 해독한 염기는 A가 된다.

문제는 어떤 염기서열이 주어졌을 때 위의 표를 참고하여 해독된 최종 염기를 출력하는 것이다.

입력

첫째 줄에 염기 서열의 길이 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 염기서열을 나타내는 길이가 N인 문자열이 주어진다.

출력

첫째 줄에 최종 염기를 출력한다.

 

예제 입력  6 AAGTCG

예제 출력  A

 

풀이

 

주어진 염기 서열의 끝 두 글자를 표에 대입한 값으로 계속 바꿔, 한 글자가 될 때까지 반복하는 문제이다.

 

AA,GG,CC,TT 처럼 서로 같은 문자는 각각 똑같은 A,G,C,T 를 출력한다.

그리고 잘 보면 표에 있는 값은 대각선을 기준으로 대칭이다.

따라서 정의해야할 분기는 16개가 아닌 6개만 지정해줘도 충분하다.

 

빠른 처리와 편의성을 위해 딕셔너리를 이용하기로 했다.

 

import sys
input = sys.stdin.readline

n = int(input())
dna = list(input().rstrip())
itp = {"AG":"C", "AC":"A", "AT":"G", "GC":"T", "GT":"A", "CT":"G"}

a,b = "", dna.pop()
for _ in range(n-1):
    a = dna.pop()
    if a == b:
        continue
        
    if a+b in itp:
        b = itp[a+b]
    else:
        b = itp[b+a]
print(b)

 

아니면 그냥 맘편하게 대각선을 제외한 12개를 딕셔너리에 넣어놓아도된다.

 

import sys
input = sys.stdin.readline

n = int(input())
dna = list(input().rstrip())
itp = {"AG":"C", "AC":"A", "AT":"G", "GC":"T", "GT":"A", "CT":"G", "GA":"C", "CA":"A", "TA":"G", "CG":"T", "TG":"A","TC":"G"}

a,b = "", dna.pop()
for _ in range(n-1):
    a = dna.pop()
    if a == b:
        continue
        
    b = itp[a+b]
print(b)