Lesson 15. Caterpillar method - CountDistinctSlices #2 (속도 개선)

1. 속도 개선 아이디어

이전 코드에서는 모든걸 하나하나씩 세고 있다. 

 

예제를 다시 보면, 

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

... 이하 생략 ...

 

이전 코드에서는 첫번째 반복에서 (3), (3, 4), (3, 4, 5)를 세고,

두번째 반복에서 (4), (4, 5)를 다시 세고 있다.

 

사실 처음에 계산한 slice에서 맨 앞 숫자인 3만을 제외하면, 두번째 반복에서 얻어지는 slice를 구할 수 있다.

즉, 두번째 반복에서 처음부터 다시 세는것이 아니라, 그냥 3만을 제외하면, 두번째 반복에서 얻을 수 있는 slice를 모두 구할 수 있다.

 

2. 문제풀이 전략

첫번째 반복문에서 3개를 얻는다

0	1	2	3	4	5	6
			true	true	true

 

두번째 반복문에서 2개를 얻는다

0	1	2	3	4	5	6
				true	true

 

세번째 반복문에서 1개를 얻는다

0	1	2	3	4	5	6
					true

 

네번째 반복문에서 2개를 얻는다.

더이상 넣을 숫자가 없다. 

이제 slice에 있는 숫자를 제거해가며 남아있는 slice 경우의 수를 찾는다.

0	1	2	3	4	5	6
		true			true

 

다섯번째 반복문에서 1개를 얻는다. 끝.

0	1	2	3	4	5	6
					true

 

위와 같은 식으로, slice는 하나씩 세지 않고,

이미 계산된 slice를 활용해서,

총 slice 개수를 구한다.

 

3. 코드 (C++)

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

    int cnt = 0;
    vector<bool> numbers(M + 1, false); //slice에 포함된 번호 확인 배열

    size_t back = 0;
    for(size_t front = 0; front < A.size(); front++)
    {
        if(front > back) back = front; //back index 조정

        while(back < A.size())
        {
            int n = A[back];
            if(numbers[n] == true)
            {
                break;
            }
            else
            {
                numbers[n] = true;
                back++;
            }
        }

        cnt += back - front; //지금까지 얻어진 slice 개수
        if(cnt > 1000000000) return 1000000000;
        
        //slice에서 맨 앞에 있는 숫자 제거
        int n = A[front];
        numbers[n] = false;
    }

    return cnt;
}

 

 

4. 결과