[2023 코딩테스트] DNA비밀번호

2023.06.17 / 새벽까지 풀었지만 시간초과.. 슬라이딩 윈도우 개념을 익히고 다시 풀어보자!
2023.06.18 / 해결완료

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        String[] sArray = br.readLine().split("");

        int[] nArray = new int[4];
        int[] copyArray = Arrays.copyOf(nArray, 4);
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            nArray[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;
        int startIndex = 0;
        int endIndex = P-1;
        int currentIndex = 0;

        while(endIndex != S) {
            if(currentIndex > endIndex) {
                if(checkAllInclude(copyArray)) {
                    count++;
                }
                copyArray = Arrays.copyOf(nArray, 4);
                startIndex++;
                endIndex++;
                currentIndex = startIndex;
            }else if(sArray[currentIndex].equals("A")) {
                copyArray[0]--;
                currentIndex++;
            }else if(sArray[currentIndex].equals("C")) {
                copyArray[1]--;
                currentIndex++;
            }else if(sArray[currentIndex].equals("G")) {
                copyArray[2]--;
                currentIndex++;
            }else if(sArray[currentIndex].equals("T")) {
                copyArray[3]--;
                currentIndex++;
            }
        }

        System.out.println(count);
    }

    public static boolean checkAllInclude(int[] nArray) {
        for(int i = 0; i < nArray.length; i++) {
            if(nArray[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

• 최초에 코드를 작성할 때 시간복잡도는 고려하지 않고 코드를 작성하였더니 결과 값은 제대로 나왔으나 시간초과가 발생했다.
• 위 코드는 이전에 학습하였던 투 포인터의 개념을 적용하여 문제를 해결하려고 한 것으로 알고리즘 방식은 다음과 같다.
  1. endIndex가 S-1과 동일하지 않으면 반복문을 계속해서 수행하도록 조건을 설정한다.
  2. 현재 배열을 가르키는 인덱스인 currentIndex가 endIndex의 값보다 클 경우 checkAllInclude메소드를 실행한다. 이 메소드는 매개변수로 받은 배열을 순차적으로 탐색하여 하나라도 0이 아닌경우는 false값을 리턴하고 그 외에는 true값을 리턴한다.
  3. 리턴받은 값이 true일 경우 count변수를 증가시키고 startIndex와 endIndex의 값을 증가시킨다.
  4. currentIndex의 값이 endIndex의 값보다 커졌으므로 다시 startIndex로 값을 초기화 시키고 배열 또한 다시 계산을 수행해야하기 때문에 copyArray의 값을 nArray값으로 세팅했다.
  5. 4번에서 적용한 방법때문에 startIndex와 endIndex의 값이 변경될때마다 새로 계산을 수행했기 때문에 시간초과가 발생한 것으로 판단하였다.

위 문제를 해결하기 위해 슬라이딩 윈도우라는 개념을 찾아보았다. 슬라이딩 윈도우를 적용한 핵심 해결방법은 고정된 문자열외에 삭제되거나 추가되는 인덱스의 값만 계산하여 모든 알파벳이 들어가있는지 확인하면 되는 문제였다.

import java.io.*;
import java.util.*;

public class Main {
    public static int result = 0;
    public static int checkSecret = 0;
    public static int[] nArray = new int[4];
    public static int[] myArray = new int[4];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        String[] sArray = br.readLine().split("");

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            nArray[i] = Integer.parseInt(st.nextToken());
            if(nArray[i] == 0) {
                checkSecret++;
            }
        }

        for(int i = 0; i < P; i++) {
            add(sArray[i]);
        }

        if(checkSecret == 4) {
            result++;
        }

        for(int i = P; i < S; i++) {
            int j = i - P;
            add(sArray[i]);
            remove(sArray[j]);
            if(checkSecret == 4) {
                result++;
            }
        }
        System.out.println(result);
    }

    public static void add(String curAlphabet) {
        switch (curAlphabet) {
            case "A":
                myArray[0]++;
                if (nArray[0] == myArray[0]) {
                    checkSecret++;
                }
                break;
            case "C":
                myArray[1]++;
                if (nArray[1] == myArray[1]) {
                    checkSecret++;
                }
                break;
            case "G":
                myArray[2]++;
                if (nArray[2] == myArray[2]) {
                    checkSecret++;
                }
                break;
            case "T":
                myArray[3]++;
                if (nArray[3] == myArray[3]) {
                    checkSecret++;
                }
                break;
        }
    }

    public static void remove(String curAlphabet) {
        switch (curAlphabet) {
            case "A":
                if (nArray[0] == myArray[0]) {
                    checkSecret--;
                }
                myArray[0]--;
                break;
            case "C":
                if (nArray[1] == myArray[1]) {
                    checkSecret--;
                }
                myArray[1]--;
                break;
            case "G":
                if (nArray[2] == myArray[2]) {
                    checkSecret--;
                }
                myArray[2]--;
                break;
            case "T":
                if (nArray[3] == myArray[3]) {
                    checkSecret--;
                }
                myArray[3]--;
                break;
        }
    }
}

• 위 문제를 해결하는데 핵심 아이디어는 다음과 같다.(백준알고리즘 문제 상 2번 예제를 통해 아이디어를 설명하겠다.)
  1. 최초 배열의 값을 셋팅하기 위해 처음부터 P까지 반복문을 수행하며 add(String curAlphabet)메서드를 호출한다. 이 메서드는 case문을 사용하여 A, C, G, T일때 myArray[i]의 값을 증가시키고 nArray[i]와 myArray[i]를 비교하여 같을 경우 checkSecret의 값을 증가시켰다. 반복문을 모두 수행 후 checkSecret의 값이 4일경우 result의 값을 증가시켰다.
  2. 슬라이딩 윈도우 개념을 적용하기 위해 P부터 S까지의 반복문을 수행한다. 첫번째 배열의 인덱스를 제거해야하기 때문에 j의 값을 설정해주어야 하는데, j의 값은 i-P로 설정한다. 동일하게 배열의 i번째 인덱스 값이 추가되고 j번째 인덱스의 값이 제거되기 때문에 add(String curAlphabet)와 remove(String curAlphabet)메서드를 호출해주고 각 반복문마다 checkSecret의 값이 4일 경우 result를 증가시켜주었다.
  3. remove(String curAlphabet)의 경우 add(String curAlphabet)의 역순이라고 생각하면 코드를 작성할 수 있을 것이다.

무작정 코드를 작성하는것이 중요한게 아니라, 시간복잡도를 고려해서 적절한 알고리즘을 선택하는것이 중요하다는 것을 알았다. 노력하자..