Algorithm - 백준 DNA 비밀번호(12891), 슬리이딩 윈도우

12891번: DNA 비밀번호

 

 

 

 

처음에는 Map을 사용하여 구현하였으나, 시간초과가 발생했다.

import java.util.*;

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

    int S = scanner.nextInt();
    int P = scanner.nextInt();
    String dnaString = scanner.next();
    HashMap<Character, Integer> minCounts = new HashMap<>();
    minCounts.put('A', scanner.nextInt());
    minCounts.put('C', scanner.nextInt());
    minCounts.put('G', scanner.nextInt());
    minCounts.put('T', scanner.nextInt());

    // 비밀번호 종류 수 계산 및 출력
    System.out.println(countPasswords(dnaString, P, minCounts));

  }

  public static int countPasswords(String dna, int pLength, HashMap<Character, Integer> minCounts) {
    // DNA 문자열 길이
    int n = dna.length();
    // 비밀번호 카운터
    int passwordCount = 0;

    // 가능한 부분문자열 순회
    for (int start = 0; start <= n - pLength; start++) {
      String subString = dna.substring(start, start + pLength);
      // 부분문자열에서 A, C, G, T 각각의 개수 체크
      HashMap<Character, Integer> counts = new HashMap<>();
      for (char c : subString.toCharArray()) {
        counts.put(c, counts.getOrDefault(c, 0) + 1);
      }

      // 주어진 최소 개수와 비교하여 조건 충족 여부 확인
      boolean b = true;
      for (char c : minCounts.keySet()) {
        if (counts.getOrDefault(c, 0) < minCounts.get(c)) {
          b = false;
          break;
        }
      }

      if (b) {
        passwordCount++;
      }
    }

    return passwordCount;
  }

}

 

 

 

특정 알고리즘을 사용하여야 한다는 것을 깨닫고 찾아보니, 슬라이딩 윈도우 알고리즘을 통하여 문제를 해결하여야 했다.

 

 

슬리이딩 윈도우

 

1차원 배열을 2회 이상 탐색할 경우, O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다.

이와 비슷한 기능을 가진 투 포인터 알고리즘도 존재한다.

둘의 차이는 슬리이딩 윈도우는 배열 길이가 고정적일 경우, 투 포인터는 배열 길이가 가변적일 경우 사용하게 된다.

오늘은 슬라이딩 윈도우를 사용해 보기로 했다.

 

 

 

import java.util.Scanner;

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

    int answer=0;
    int N = sc.nextInt();
    int P = sc.nextInt();

    char[] dna = sc.next().toCharArray();  //문자열을 문자 배열로 변환


    int[] check = new int[4];  // 필요한 문자 갯수 저장
    for (int i = 0; i < 4; i++) {
      check[i] = sc.nextInt();
    }

    // 첫 P개의 문자열에서 A, C, G, T 각각의 개수 확인
    int[] countAlph = new int[4];
    for (int j = 0; j < P; j++) {
      switch (dna[j]) {
        case 'A': countAlph[0]++; break;
        case 'C': countAlph[1]++; break;
        case 'G': countAlph[2]++; break;
        case 'T': countAlph[3]++; break;
      }
    }

    // 비밀번호 후보
    for (int i = 0; i <= N-P; i++) {
      boolean flag = false;
      // 조건에 부합하는지 확인
      for(int j=0; j<4; j++) {
        if(countAlph[j] < check[j]) {
          flag = true;
          break;
        }
      }
      if (!flag) // 사용 가능한 비밀번호
        answer++;
      if(i==N-P) break;

      countAlph[position(dna[i])]--;  //맨 앞 문자 제거
      countAlph[position(dna[i+P])]++;  //뒤 문자 추가
    }

    System.out.println(answer);

  }

  // 각 문자 위치 확인
  private static int position(char alph) {
    switch(alph) {
      case 'A' : return 0;
      case 'C' : return 1;
      case 'G' : return 2;
      case 'T' : return 3;
    }
    return -1;
  }

}

 

 

 

O(N^2) 이상 걸릴 시간 복잡도를 슬라이딩 윈도우 알고리즘을 통해 O(N)로 단축시켜 무사히 해결했다.

슬라이딩 윈도우의 특징은 맨 앞의 값은 제거, 맨 뒤에에 값을 추가하여 순차적으로 조회하는 방식이었다.