구간 합

- 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 특정한 구간의 합을 구하기 위한 알고리즘

- 합 배열 정의 : 해당 인덱스까지의 값을 더한 값을 해당 인덱스의 값으로 갖는 배열
ex) s[i] = s[i-1] + a[i]

- 구간 합을 구하는 방법 
: 합 배열 - 원하는 구간외의 구간 합을 뺀 값
: if 10개의 인덱스를 갖는 배열, 5~10 구간 합을 구하는 방법
: s[10] - s[4] = a[5] + a[6] + a[7] + a[8] + a[9] +a[10] 

 

1. 문제 풀이 

- 백준 문제 11659 - 실버 3

N 개의 숫자의 특정한 구간의 합을 구하는 문제이다. 이는 구간합 문제로 합 배열으 생성하여 해당 배열의 값의 차이를 이용해 구할 수 있다. 

1. N개의 숫자와 M번 반복할 변수를 받고 N개의 숫자를 입력받는다. 

2. numbers 배열에 N개의 숫자를 입력받고 sum 배열에 이전 인덱스의 값 + 입력받는 숫자 값을 저장한다. 

3. M번 반복하여 특정한 구간을 입력받는다. 

4. sum 배열의 끝구간 값 - (시작구간-1) 값으로 구간 합을 구한다. 
ex) sum[끝 구간] - sum[시작구간-1]

---

정답코드

 

import java.util.Scanner;

class No_11659 {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        long numbers[] = new long[number];
        long sum[] = new long[number];

        int repeat = sc.nextInt();

        // 숫자 입력 받기 + 합 배열 생성
        for (int i = 0; i < number; i++) {
            numbers[i] = sc.nextInt();
            if (i == 0) {
                sum[i] = numbers[i];
            } else {
                sum[i] = sum[i - 1] + numbers[i];
            }
        }
        // 각 구간 합 구하기
        for (int i = 0; i < repeat; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            if (start == end) {
                System.out.println(numbers[start - 1]);
            } else if (start == 1) {
                System.out.println(sum[end - 1]);
            } else {
                System.out.println(sum[end - 1] - sum[start - 2]);
            }
        }

        return;
    }
}

 

- 백준 문제풀이 2018번 - 실버 5 (투 포인터 )

자연수 N을 입력받아서 연속되는 수의 합으로 자연수 N을 만들 수 있는 방법의 개수를 구하는 문제이다. 

이는 투 포인터를 이용한 문제로 연속된 수의 값이므로 위와 같이 구간 합을 구하는 문제이다. 하지만 구간 합이 특정한 자연수 N의 값과 같아야 하므로 3가지 경우를 나누어 구간의 범위를 수정하면서 구할 수 있다. 

1. 자연수 N 을 입력받는다. 

2. 시작 인덱스 = 1, 끝 인덱스 = 1 으로 초기화한 후 해당 구간의 합을 sum 변수에 저장한다. 

3. while 문을 이용하여 시작 인덱스의 값이 자연수 N의 값과 같아질 때까지 반복한다. 

4. while 문 안에 조건을 작성하여 가능한 경우의 수를 센다.
  4-1) 시작 인덱스에서 끝 인덱스까지의 구간 합이 자연수 N보다 작은 경우 끝 인덱스의 값을 더한다. 
  4-2) 시작 인덱스에서 끝 인덱스까지의 구간 합이 자연수 N이랑 같은 경우 count 값을 증가시키고 끝 인덱스의 값을 sum 에 더함
  4-3) 시작 인덱스에서 끝 인덱스까지의 구간 합이 자연수 N보다 큰 경우 시작 인덱스의 값을 더한다. 

5. 4의 경우에 따라 count 값을 세고 그 값을 출력한다. 

---

정답코드

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

class No_2018 {
    public static void main (String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int num = Integer.parseInt(stringTokenizer.nextToken());

        int startInd = 1;
        int endInd = 1;
        int sum = 1;
        int count = 1;
        while( startInd != num) {
            // sum 값이 num 값 이하인 경우
            if (sum < num) {
                endInd++;
                sum += endInd;
            }
            // sum 값이 num 이랑 같을 때
            else if ( sum == num) {
                endInd++;
                sum += endInd;
                count++;
            }
            // sum 값이 num 값보다 큰 경우
            else {
                sum -= startInd;
                startInd++;
            }
        }
        System.out.println(count);
        return;
    }
}

 

- 백준 문제풀이 12891번 - 실버 2 (슬라이딩 윈도우)

길이가 N 인 문자열을 입력받아서 길이가 M인 암호 문자열을 만들 수 있는 경우의 수를 구하는 문제이다. 여기서 핵심은 암호 문자열은 입력받은 문자열의 연속적인 문자열 중 하나이다.

추가적으로 다음으로 입력받는 A,C,G,T 의 개수를 충족하는 암호 문자열이여야 한다. 

암호 문자열이 연속적인 문자열이라는 점을 이용해서 슬라이딩 윈도우 방식으로 문제를 해결할 수 있다.

1. 총 문자열의 개수, 암호 문자열의 개수를 입력받고, 문자열을 입력받는다. 추가적인 조건으로 충족해야 하는 A,C,G,T 의 개수를 입력받는다.

2. 문자열의 첫번째 (시작 인덱스)문자부터 암호 문자열의 개수번째(끝 인덱스) 문자를 A,C,G,T 와 비교하며 A,C,G,T의 개수를 저장하는 배열을 생성한다. 

3. 배열 생성 후 끝 인덱스의 값이 총 문자열의 개수와 같아지 때까지 반복문을 돌린다. 

4. 반복문 내에서는 
  - 먼저 입력받는 A,C,G,T 조건을 충족해야하는 배열과 2번에서 생성한 문자열 A,C,G,T 개수 배열을 비교하여 같은 값이면 count 를 증가시킨다. 
  - 다음으로 시작 인덱스에 해당하는 문자가 A,C,G,T 문자와 같은지 확인하여 2번에서 생성한 배열에서 같은 문자의 개수를 감소시키고 시작 인덱스의 값을 증가시킨다. 
  - 다음으로 끝 인덱스를 증가시킨 후 증간한 끝 인덱스에 해당하는 문자가 A,C,G,T 문자와 같은지 확인하여 2번에서 생성한 배열에서 같은 문자의 개수를 증가시킨다. 

5. 반복문이 종료된 후 count 값을 출력한다. 

---

정답코드

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

class No_12891 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        // 입력받기
        int strLen = sc.nextInt();
        int secretLen = sc.nextInt();
        String str = sc.next();
        String strs[] = str.split("");
        // acgt 개수 세기
        int acgt[] = new int[4];
        for (int i = 0; i < 4; i++) {
            acgt[i] = sc.nextInt();
        }

        int strAcgt[] = new int[4];

        int startInd = 0;
        int endInd = secretLen - 1;
        // acgt 개수 세기
        for (int i = 0; i < secretLen; i++) {
            if (strs[i].equals("A")) {
                strAcgt[0]++;
            } else if (strs[i].equals("C")) {
                strAcgt[1]++;
            } else if (strs[i].equals("G")) {
                strAcgt[2]++;
            } else if (strs[i].equals("T")) {
                strAcgt[3]++;
            }
        }

        int count = 0;
        while (endInd != strLen) {
            int same = 0;
            for (int i = 0; i < 4; i++) {
                if (acgt[i] <= strAcgt[i]) { same++;}
            }

            if (same == 4) { count++;}

            if (strs[startInd].equals("A")) {
                strAcgt[0]--;
            } else if (strs[startInd].equals("C")) {
                strAcgt[1]--;
            } else if (strs[startInd].equals("G")) {
                strAcgt[2]--;
            } else if (strs[startInd].equals("T")) {
                strAcgt[3]--;
            }
            startInd++;
            endInd++;
            if (endInd != strLen) {
                if (strs[endInd].equals("A")) {
                    strAcgt[0]++;
                } else if (strs[endInd].equals("C")) {
                    strAcgt[1]++;
                } else if (strs[endInd].equals("G")) {
                    strAcgt[2]++;
                } else if (strs[endInd].equals("T")) {
                    strAcgt[3]++;
                }
            }

        }
        System.out.println(count);
        return;
    }
}