자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(연속부분수열_복합문제)

 

 

4. 연속부분수열(복합문제)

 

예시 입력 1 

8 6
1 2 1 3 1 1 1 2

예시 출력 1

3

 

 

2중 포문으로 풀면 시간복잡도가 O(N²)인데,

입력값이 십만이 넘기 때문에, i부터 쫘악 도는게 비효율적이다. 입력 제한을 보는 순간 O(N²)은 안되겠구나라고 판단해야한다.

O(N²)을 O(N)으로 풀어내는 능력을 키워야 합니다.

 

 

내가 푼 틀린 풀이(Time: 1947ms Memory: 34MB- Time Limit Exceeded)

 

2중 포문만 안쓰면 되는 줄 알았는데, 결국에는 다시 2번째 if분기처리에서 for문을 재 순회하게 되므로 시간 초과가 나왔다.

import java.util.Scanner;

public class Main {
    public int solution(int n, int m, int[] arr) {
        int answer = 0;

        int start = 0;
        int sum = arr[start];
        for (int i = start+1; i < n; i++) {
            sum += arr[i];
            if (sum == m) {
                answer++;
                start ++;
                i = start;
                sum = arr[start];
            }
            if (i == n-1) {
                start ++; // 1
                i = start; //2
                sum = arr[start];
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n,m,arr));
    }
}

 

투포인터랑 슬라이딩 윈도우 2개를 사용해봅니다

 

투포인터 : lt, rt

어떤 특정 연속 부분의 구간을 lt부터 rt까지 연속된 합이 특정 숫자 M이 되는가를 확인하는 알고리즘으로 구현해야한다

맨 처음에는 lt부터 rt까지의 합 , 0부터 0까지의 합을 구한다.

sum이 m보다 작으면 rt를 증가하면서 계속 sum에 누적합니다.

rt는 처음 한번만 누적하고 확인했는데, 그 다음부터는 증가하고 누적하고 확인해야 합니다. 그래야 구간합이 됩니다.

 

그런데 lt부터 rt까지 구간의 합이 m보다 커지면 rt를 증가할 필요 없이, lt가 증가하면서 빼야합니다.

 

lt값을 빼고 다시 m이랑 같은지 확인한 뒤 카운팅 합니다.

그리고 sum값이 m보다 크거나 같아도 lt를 증가하고 sumd에서 빼야 합니다.

이제 sum이 6보다 작아지면 rt를 증가합니다. 증가하다가 누적합이 다시 6이랑 같으면 lt를 증가하고 빼줍니다.

이렇게 해서 rt가 원소 끝까지 갔는데 sum이 m보다 작으면 lt의 값을 빼도 소용 없다.

그런데 m보다 크면 lt를 증가시키고 값을 뺍니다.

 

강의 풀이(Time: 776ms Memory: 34MB)

import java.util.Scanner;

public class Answer {
    public int solution(int n, int m, int[] arr) {
        int answer = 0, sum = 0, lt = 0; // 카운팅, sum, lt값을 0으로 초기화
        for (int rt = 0; rt < n; rt++) { // 증가하고
            sum += arr[rt]; // 더하고
            if (sum == m) answer++; // 확인
            // sum이 m보다 작으면 lt가 증가하고 빼줘야 하는데,
            // 하나만 뺀다고 아직 M보다 클 수도 있으니까 while문 사용
            while (sum >= m) {
                sum -= arr[lt++];
                if (sum == m) answer++; // 확인
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Answer T = new Answer();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, m, arr));
    }
}