글 읽기 - 시간 복잡도 관련질문

bassrkd 1년 전 0

시간초과가 되어 질문합니다.

아래 소스코드의 시간 복잡도는 O(n^2)인지, O(n)인지 궁금합니다.

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

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

        char[] DNA_arr = new char[S];
        int[] DNA_num_arr = new int[4];
        int[] DNA_num_arr_temp = new int[4];




        st = new StringTokenizer(bf.readLine());
        String DNA = st.nextToken();
        DNA_arr = DNA.toCharArray();



        char[] DNA_Standard_arr = {'A','C','G','T'};


        st = new StringTokenizer(bf.readLine());
        for (int o =0; o < 4; o++){
            DNA_num_arr[o] = Integer.parseInt(st.nextToken());
        }

        for (int w = 0; w < 4; w++){
            DNA_num_arr_temp[w] = DNA_num_arr[w];
        }


        int i = 0;
        int j = P-1;
        int answer =0;

        while (j < S){
            for (int k =i; k <= j; k++){
                for (int q = 0; q < 4; q++){
                    if (DNA_num_arr_temp[q] == 0) continue;
                    else if (DNA_arr[k] == DNA_Standard_arr[q]) {
                        DNA_num_arr_temp[q]--;
                    }
                }
            }

            int check_DNA_count = 0;
            for (int p =0; p < 4; p++){
                if (DNA_num_arr_temp[p] > 0) check_DNA_count += DNA_num_arr_temp[p];
            }

            if (check_DNA_count == 0) answer++;
            for (int w = 0; w < 4; w++){
                DNA_num_arr_temp[w] = DNA_num_arr[w];
            }
            i++;
            j++;

        }


        System.out.println(answer);



    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 복잡도 관련질문

bassrkd 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말