문제
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인 문자열이 주어진다.
출력
첫째 줄에 최종 염기를 출력한다.
풀이 및 회고
풀이
주어진대로 구현하면 되는 문제이다. 단, 파이썬의 경우 문자열 슬라이싱 및 문자열 대체 방식으로 풀 경우 시간초과가 발생하므로 문자열을 리스트로 바꾼 뒤 푸는 것을 권장한다.
회고
아니 슬라이싱 시간초과가 뜰줄은 몰랐다. 심지어 방식에 문제가 있는 줄 알고 DP로 접근했다가 메모리 초과가 떴다. 결국은 리스트로 바꿔서 푼.. 다른사람들은 어케 푼거여;;
코드
DNA_DIC = {
"AA": "A",
"AG": "C",
"AC": "A",
"AT": "G",
"GA": "C",
"GG": "G",
"GC": "T",
"GT": "A",
"CA": "A",
"CG": "T",
"CC": "C",
"CT": "G",
"TA": "G",
"TG": "A",
"TC": "G",
"TT": "T",
}
n = int(input())
s = list(input())
for i in range(n - 2, -1, -1):
s[i] = DNA_DIC[s[i] + s[i + 1]]
s[i + 1] = ""
print(s[0])
