[백준] 1672 DNA 해독

문제

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

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

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

입력

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

출력

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

내 풀이

n = int(input())
gene = input().strip()

def pair(a, b):
    if a == b:
        return a
    elif {a, b} == {"A", "C"} or {a, b} == {"G", "T"}:
        return "A"
    elif {a, b} == {"A", "G"}:
        return "C"
    elif {a, b} == {"A", "T"} or {a, b} == {"C", "T"}:
        return "G"
    elif {a, b} == {"C", "G"}:
        return "T"

answer = gene
while len(answer) > 1:
    i = len(answer)
    part1 = answer[:i-2]
    part2 = pair(answer[i-2], answer[i-1])
    answer = part1 + part2
    
print(answer)

처음에는 위와 같이 풀었다가 시간 초과를 받았는데, 이후에도 약간씩 고쳤음에도 불구하고 시간 초과를 피할 수 없었다. 위의 풀이는 매번 set을 생성하고 비교하는 방식이라 비효율적이다. 게다가 answer 문자열을 계속 잘라 붙이기 때문에 메모리 사용까지 비효율적이다.

그러나 아래 코드처럼 딕셔너리로 결합 규칙을 미리 만들어 놓으면 딕셔너리의 키로 접근하면 if 문으로 일일이 비교할 때보다 훨씬 빠르다. 게다가 입력받은 염기서열을 리스트로 변환하여 pop()을 사용하면 $O(1)$ 연산으로 매우 빠르게 처리할 수 있다. 이 코드는 불필요하게 set을 생성하거나 if문으로 계속 비교하지 않아도 되기 때문에 시간 초과 없이 정답을 받을 수 있다.

n = int(input())
gene = list(input().strip())

# 결합 규칙 딕셔너리
table = {
    ('A', 'A'): 'A',
    ('A', 'G'): 'C',
    ('A', 'C'): 'A',
    ('A', 'T'): 'G',
    ('G', 'A'): 'C',
    ('G', 'G'): 'G',
    ('G', 'C'): 'T',
    ('G', 'T'): 'A',
    ('C', 'A'): 'A',
    ('C', 'G'): 'T',
    ('C', 'C'): 'C',
    ('C', 'T'): 'G',
    ('T', 'A'): 'G',
    ('T', 'G'): 'A',
    ('T', 'C'): 'G',
    ('T', 'T'): 'T'
}

# 뒤에서부터 결합
while len(gene) > 1:
    a = gene.pop()
    b = gene.pop()
    gene.append(table[(b, a)])

print(gene[0])

코멘트

브론즈지만 최적화하기 꽤 까다로운 문제였다. 자세한 설명은 풀이에서.

[백준] 1672 DNA 해독

문제

입력

출력

내 풀이

코멘트

References