Lesson8. Leader - EquiLeader

EquiLeader - Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same.

https://app.codility.com/programmers/lessons/8-leader/equi_leader/

문제요약

N개의 정수배열 A에 주어진다. A의 길이의 절반보다 많이 등장하는 수를 leader라고 한다. 어떤 index S에 대해 0<=S<N-1일 때, A[0], A[1]...,A[S]와 A[S+1], A[S+2], ...,A[N-1]이 동일한 leader를 갖는다면 S를 equi leader라고 한다.

주어진 A의 equi leader의 수를 계산한다.

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

O(N)에 해결하는게 관건인 문제. A를 임의의 두 부분으로 나눠서 확인한 뒤에 왼쪽으로 하나를 이동해서 확인한다고 할 때, 왼쪽에 leader가 있는지 확인하려면 이전의 leader와 새로 이동한 값에 대해서 leader인지를 확인하면 된다. 이전에 leader였던 값이 그대로 유지 될 수도 있고 이동한 값에 의해 leader가 생길 수도 있기 때문이다. 그리고 왼쪽에 leader가 존재한다면 오른쪽 부분에 해당 값이 동일하게 leader인지를 판단한다.

이 때 각 등장 횟수를 미리 계산해 놓고 왼쪽과 오른쪽을 별도로 운영하면서 이동하는 값에 대해서만 +-1을 해주면 각 단계별로 상수시간에 leader의 존재 유무를 판단할 수 있다. A의 각 index(0~N-2)에 대해 계산을 해야 하므로 전체 시간은 O(N)이 된다.