DNA 해독
면접 대비시간 제한5초메모리 제한16 MB
DNA 문자열의 마지막 두 염기를 정해진 표에 따라 계속 합쳐서 하나의 염기만 남을 때까지 줄이는 문제입니다.
문제
DNA 염기서열은 A, G, C, T로 이루어진 문자열이다. 이 염기서열을 아래 해독표에 따라 한 글자가 남을 때까지 줄이려고 한다.
현재 염기서열의 오른쪽 끝 두 염기를 차례대로 X, Y라고 하자. 표에서 X가 있는 행과 Y가 있는 열이 만나는 칸의 염기 하나로 두 염기를 바꾼다. 이 과정을 염기서열의 길이가 1이 될 때까지 반복한다.
주어진 염기서열을 해독했을 때 마지막에 남는 염기를 출력하라.
입력
첫째 줄에 염기서열의 길이 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 길이가 N인 염기서열이 주어진다.
출력
첫째 줄에 최종 염기 하나를 출력한다.