[Baekjoon/JAVA] 1672번 - DNA 해독

Baekjoon Online Judge

문제로 이동

 

문제

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인 문자열이 주어진다.

 

출력

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

 

---

예제 입력	예제 출력
6 AAGTCG	A

---

풀이

import java.util.Scanner;

public class Main {
    static char agct[] = {'A', 'G', 'C', 'T'};

    static char arr[][] = { // 염기서열 해독표
            {'A', 'C', 'A', 'G'},
            {'C', 'G', 'T', 'A'},
            {'A', 'T', 'C', 'G'},
            {'G', 'A', 'G', 'T'}
    };

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt(); // 염기 서열의 길이
        String s = in.next(); // 염기서열을 나타내는 길이가 N인 문자열

        int num = charToInt(s.charAt(N - 1));

        for (int i = N - 1; i > 0; i--) {
            int idx1 = charToInt(s.charAt(i - 1));
            int idx2 = num;

            // 제일 끝에 있는 두 개의 염기를 하나의 염기로 바꾸기
            char c = arr[idx1][idx2];
            num = charToInt(c);
        }

        // 출력
        System.out.println(agct[num]);
    }

    // 문자를 agct의 순서에 맞춰 숫자로 바꿔준다.
    public static int charToInt(char c) {
        int num = 0;

        for (int i = 0; i < 4; i++) {
            if (c == agct[i]) {
                num = i;
                break;
            }
        }

        return num;
    }
}

일단 행과 열 모두 AGCT 순서이기에 이를 배열(agct[])에 순서대로 저장해서 각 문자가 담당하는 인덱스 번호를 배열을 통해 구할 수 있게끔 했다. 그리고 염기서열 해독표를 arr[]에 저장했다.

 

// 문자를 agct의 순서에 맞춰 숫자로 바꿔준다.
    public static int charToInt(char c) {
        int num = 0;

        for (int i = 0; i < 4; i++) {
            if (c == agct[i]) {
                num = i;
                break;
            }
        }

        return num;
    }

배열 agct[]에 순서에 따라 문자를 숫자로 변환해주는 함수이다. agct의 문자 중 c와 같다면 그 인덱스 번호를 return한다.

 

        int num = charToInt(s.charAt(N - 1));

        for (int i = N - 1; i > 0; i--) {
            int idx1 = charToInt(s.charAt(i - 1));
            int idx2 = num;

            // 제일 끝에 있는 두 개의 염기를 하나의 염기로 바꾸기
            char c = arr[idx1][idx2];
            num = charToInt(c);
        }

num은 두 개의 염기를 하나의 염기로 변환한 결과를 숫자로 변환한 것을 저장하는 변수이다.

idx1은 An-1(문자열의 맨 뒤에서 두번째)의 문자를 숫자로 변환한 결과를 저장하는 변수이다.

idx2는 An(문자열의 맨 뒤)의 문자를 숫자로 변환한 결과이며, 이 값은 num에서 넘겨 받는다. 그 이유는 맨 뒤의 2개의 염기를 변환한 결과(num)는 문자열의 가장 뒤에 2개의 염기 대신 붙어있게 되어 An이 되기 때문이다.