Qualification Round. Problem 2 The Secondary Structure of RNA

RNA sequence를 주고 해당 rna의 모든 염기들이 쌍을 이루는 secondary structure를 형성할수있는지를 묻는 문제이다. 괄호문제랑 사실상 똑같다. Stack에 염기를 하나씩 넣으면서 넣기직전에 stack의 제일 위에있는 염기와 넣을 염기가 쌍을 이루면 제일 위의 염기를 pop하면 된다. 아니면 push한다.

from functools import reduce

input = input()

# with open('6') as f:
#     input = f.read().strip()

combine = {'A': 'U', 'U': 'A', 'C': 'G', 'G': 'C'}

pair_stack = []
for base in input:
    if len(pair_stack) == 0:
        pair_stack.append(base)
    else:
        if pair_stack[-1] == combine[base]:
            pair_stack.pop(-1)
        else:
            pair_stack.append(base)

if len(pair_stack) == 0:
    print('perfect')
    exit()
if len(pair_stack) == 1:
    print('almost perfect')
    exit()
elif len(pair_stack) % 2 == 1:
    spl_idx = int(len(pair_stack) / 2)
    pre_stack = reversed(pair_stack[0:spl_idx])
    post_stack = pair_stack[spl_idx+1:]
    pair_result = reduce(lambda a, b: a and b, map(lambda pair: combine[pair[0]] == pair[1], zip(pre_stack, post_stack)))
    if pair_result == True:
        print('almost perfect')
        exit()
print('imperfect')

 

문득 생각해보기엔 너무 greedy하게 매칭되어 문제가 있을것같다. 하지만 조금만 생각해보면 상관없다는 것을 알 수 있다. 어차피 complete하다면 어떤 염기를 기점으로 좌우대칭인 형태일 것이기 때문이다.

 

ATTCGCGAAT를 생각해보면

almost perfect일경우는 rna를 스택에 넣고빼는것이 완료된 후 stack이 홀수인지, 홀수라면 가운데것을 제거했을때 스택 위아래로 대칭인지를 체크해보면 된다.