문제
A, G, C, T로 이루어진 DNA 문자열이 주어지고 4×4 결합 규칙표가 있다. 문자열의 마지막 두 문자를 규칙에 따라 하나로 합치는 과정을 반복하여 최종 남는 문자를 구하라.
입력
첫째 줄에 문자열 길이 N, 둘째 줄에 DNA 문자열이 주어진다.
출력
최종 남는 하나의 문자를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 AC | A |
풀이
문자열을 뒤집어서 앞에서부터 순서대로 결합하면, 원래 문자열의 뒤에서부터 결합하는 것과 동일한 효과를 얻는다.
- 16가지 결합 규칙(AA→A, AG→C, ...)을 딕셔너리로 정의한다
- 문자열을 뒤집는다 (뒤에서부터 결합해야 하므로)
- 첫 번째 문자를 시작으로, 다음 문자와 결합 규칙을 적용하여 하나의 문자로 축소한다
- 마지막까지 반복하면 남는 문자 하나를 출력한다
핵심 아이디어: 뒤에서부터 두 문자씩 결합하는 것을 문자열 뒤집기 + 앞에서부터 순회로 치환하면 한 번의 순회로 O(N)에 해결된다.
코드
DNA = {
"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 = input().rstrip()
S = "".join(reversed(list(S)))
tmp = S[0]
for i in range(1, N):
tmp = DNA[tmp + S[i]]
print(tmp)복잡도
- 시간: O(N)
- 공간: O(N)