Lesson 15. Caterpillar method - CountDistinctSlices #1

 

 

 

 

 

 

 

 

1. 문제

An integer M and a non-empty array A consisting of N non-negative integers are given. All integers in array A are less than or equal to M.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The slice consists of the elements A[P], A[P + 1], ..., A[Q]. A distinct slice is a slice consisting of only unique numbers. That is, no individual number occurs more than once in the slice.

For example, consider integer M = 6 and array A such that:
A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2

There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 3), (3, 4) and (4, 4).
The goal is to calculate the number of distinct slices.

Write a function:
  int solution(int M, vector<int> &A);

that, given an integer M and a non-empty array A consisting of N integers, returns the number of distinct slices.
If the number of distinct slices is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given integer M = 6 and array A such that:
A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2
the function should return 9, as explained above.

Write an efficient algorithm for the following assumptions:
  - N is an integer within the range [1..100,000];
  - M is an integer within the range [0..100,000];
  - each element of array A is an integer within the range [0..M].

 

배열의 부분 집합(slice)을 구하는 문제.

slice는 (P, Q)로 나타낼 수 있으며, \( 0 \leq P \leq Q < N \) 조건을 가진다. (N: 배열 크기)

단, slice에는 중복값이 포함되면 안된다.

 

slice 개수가 1,000,000,000을 초과할 경우,

1,000,000,000을 return 한다.

 

예시) return 9

A[0]	A[1]	A[2]	A[3]	A[4]
3	4	5	5	2

 

(0, 0) = 3

(0, 1) = 3, 4

(0, 2) = 3, 4, 5

(1, 1) = 4

(1, 2) = 4, 5

(2, 2) = 5

(3, 3) = 5

(3, 4) = 5, 2

(4, 4) = 2

 

총 9개로 나눌 수 있다.

 

2. 매개변수 조건

• Vector A 크기(N): 1 ~ 100,000
• Vector A 요소 값 범위: 0 ~ M
• M: Vector A의 요소가 가질 수 있는 최대값

 

3. 문제풀이 전략 및 예제분석

이미 slice에 포함되어 있는지 확인하기 위한 vector<bool>를 만들고,

vector A값을 하나씩 추가해가며, slice 개수를 구한다.

 

A[0] = 3

0	1	2	3	4	5	6
			true

 

A[1] = 4

0	1	2	3	4	5	6
			true	true

 

A[2] = 5

0	1	2	3	4	5	6
			true	true	true

 

A[3] = 5, 이미 slice에 있으므로, 중지

 

A[1]부터 다시 시작

0	1	2	3	4	5	6
				true

0	1	2	3	4	5	6
				true	true

 

A[3] = 5, 이미 slice에 있으므로, 중지

A[2]부터 다시 시작

 

A의 마지막 요소에서 시작할때까지 위 작업을 반복한다. 

 

4. 코드 (C++)

int solution(int M, vector<int> &A) {

    int cnt = 0;
    for(size_t i = 0; i < A.size(); i++)
    {
        vector<bool> numbers(M + 1, false); //slice에 포함된 번호 확인 배열
        for(size_t j = i; j < A.size(); j++)
        {
            int idx = A[j];
            if(numbers[idx]) break; //중지
            numbers[idx] = true;
            cnt++;
            if(cnt > 1000000000) return 1000000000;
        }
    }

    return cnt;
}

 

 

5. 결과