[슬라이딩윈도우] 백준 12891번

 

문제

문자열 {A, C, G ,T}인 문자열만 주어지는 상황
1. 문자열 길이(S)를 입력 받고, 그 중에 부분 문자열(P)을 가지고 비밀번호를 만듬
2. 부분 문자열중에서 비밀번호를 만들 때,A,C,G,T 각각의 만족하는 최소 조건이 존재
3. 최소 조건을 만족하면 비밀번호를 만들 수 있음 (해당 개수 세기)
4. 2초이내,  (1 <= P <= S <= 1,000,000)

ex) A C G T A C G G T A C C (주어진 문자열)
(A (2개), C(0개), G(1개), T(1개) 이상 조건 충족)
->해당 조건을 만족하는, 비밀번호 만들 수 있는 개수 구하기

 

문제분석

• 1,000,000개 이므로, O(n)으로 시간복잡도를 가져야함
• 슬라이딩 윈도우를 이용하여, 부분문자열을 표현
• 조건에 맞는 비밀번호 생성 문자를 이용하여, 몇개를 만들 수 있는지 구현

[슬라이딩 윈도우]
(부분문자열 개수 : 4개)
arr -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10  (첫번째 부분)
arr -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (두번째 부분)
arr -> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (세번째 부분)
...

 

슈도코드

char_size(문자열크기) part_size(부분 문자열 크기)
arr (원본 문자열 저장)
condition (문자열 최소 개수 조건)

myArr(부분문자열에서 뽑은 개수 배열)

for(0에서 첫 part_size까지)
{
    myArr추가
}
if( 최소 문자열 개수 조건에 만족하는지 확인 )
{
    비밀번호 만족 개수 증가
}

for ( i를 part_size에서 char_size까지 반복 )
{
    j 선언 (i - part_size)
    한칸씩 이동하며, 제거될 문자와 추가될 문자 처리
    if ( 최소 문자열 개수 조건에 만족하는지 확인 )
    {
         비밀번호 만족 개수 증가
    }
}

결과값 출력


private static boolean check 함수 ( 최소 문자열 개수 조건 만족 확인 )
private static void Add 함수 ( 부분문자열에 새롭게 포함되는 문자 추가 )
private static void Remove 함수 ( 부분문자열에서 제거되는 문자 제거 )

 

구현

• String 함수 : toCharArray()
  • toCharArray()의 경우, 해당 문자열을 char로 바꾸어 배열에 저장해줌
  • "ABCD" -> {'a','b','c','d'}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class App {

    static int[] myArr;
    static int[] condition;

    public static void main(String[] args) throws Exception {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        
        int char_size = 0;
        int part_size = 0;
        if (st.hasMoreTokens()){
            char_size = Integer.parseInt(st.nextToken());
            part_size = Integer.parseInt(st.nextToken());
        }
        
        char[] arr = new char[char_size];
        arr = buf.readLine().toCharArray();
       
        condition = new int[4];
        st = new StringTokenizer(buf.readLine());
        for (int i =0; i < 4; i++) {
            condition[i] = Integer.parseInt(st.nextToken());
        }
         
        int result = 0;
        myArr = new int[4];
        
        //초기화 문자열
        for (int i = 0; i< part_size; i++){
            Add(arr[i]);
        }
        if (check(condition,myArr)){
                result++;
        }


        for (int i =part_size; i< char_size; i++){
            int j = i - part_size;
            Add(arr[i]);
            Remove(arr[j]);
            if (check(condition, myArr)){
                result++;
            }
        }

        System.out.println(result);
        buf.close();

    }

    private static boolean check(int[] condition, int[] myArr){
        for (int i =0; i<4;  i++){
            if(myArr[i] >= condition[i]){
                continue;
            }else{
                return false;
            }
        }
        return true;
    }

    private static void Add(char character){
        switch(character){
            case 'A':
                myArr[0]++;
                break;
            case 'C':
                myArr[1]++;
                break;
            case 'G':
                myArr[2]++;
                break;
            case 'T':
                myArr[3]++;
                break;
        }
    }

    private static void Remove(char character){
        switch(character){
            case 'A':
                myArr[0]--;
                break;
            case 'C':
                myArr[1]--;
                break;
            case 'G':
                myArr[2]--;
                break;
            case 'T':
                myArr[3]--;
                break;
        }
    }
    
}