문제
A non-empty array A consisting of N integers is given.
The leader of this array is the value that occurs in more than half of the elements of A.
An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.
For example, given array A such that:
A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2we can find two equi leaders:
0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.
The goal is to count the number of equi leaders.
Write a function:
function solution(A);
that, given a non-empty array A consisting of N integers, returns the number of equi leaders.
For example, given:
A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2the function should return 2, as explained above.
Write an efficient algorithm for the following assumptions:
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].
문제해석
하나의 배열이 주어지는데 그 배열을 두개로 나누었을때 두개로 나눈 배열의 리더가 동일한 개수를 구하는 문제이다.
리더가 될 수 있는 조건은 각 배열에서 가장 많은 요소이어야하고, 각 배열의 반보다 많아야한다.
하나의 배열을 A[0]과 A[1,..., A.length-1]부터 A[0,..., A.length-2]와 A[A.length-1]까지 나눠서 각각의 배열의 리더값을 찾고, 그것이 동일한지 확인해 일치한다면 카운팅해서 최종 카운팅 값을 구하는 문제이다.
문제풀이
일단 각각의 객체로 만들어 비교하는 방법도 있지만 범위를 보면 [−1,000,000,000..1,000,000,000]라고 주어지기 때문에 최대한 효율성 높은 코드로 구해야한다.
먼저 오른쪽에서 왼쪽으로 하나씩 옮겨 리더값을 각각 찾고 리더값이 같다면 카운팅해주는 로직을 작성할 것이다.
- 오른쪽에 해당하는 값을 객체로 만들어서 key를 요소로 key에 해당하는 개수를 value로 만들어준다.
- 그리고 필요한 것은 왼쪽으로 옮길 객체와 왼쪽의 리더, 리더를 찾을 수 있도록 카운팅할 카운트 변수, 마지막으로 왼쪽의 요소들의 담긴 배열의 길이(리더 값은 배열의 반보다 많아야 하기 때문에 길이를 알아야한다. 객체로 값을 비교해주고 있기 때문에 길이는 따로 지정해야 한다.)
- 처음 주어지는 배열 A를 하나씩 돌면서 오른쪽과 왼쪽의 객체를 변경한다.
- 오른쪽 객체를 왼쪽으로 하나씩 옮기고, 오른쪽의 길이와 해당하는 값을 하나씩 줄여주고, 반대로 왼쪽의 길이와 값을 하나씩 올려준다.
- 그리고 해당하는 값을 왼쪽 객체에서 찾아 key를 왼쪽의 리더값으로 지정하고, key에 해당하는 value를 카운트로 지정한다.
- 왼쪽 리더값을 오른쪽 key값으로 찾아 그에 해당하는 value값이 오른쪽 길이의 반보다 크고, 왼쪽 카운트 값이 왼쪽 길이의 반보다 크면 둘다 리더값이 동일하고, 배열의 절반보다 크기 때문에 리더에 해당한다.
- 리더에 조건에 맞을 때마다 전체 카운팅을 하나씩 해서 배열을 최종적으로 다 돌았을때 값을 리턴해주다.
코드
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
let answer = 0
let rightobj = {};
let rightLength = A.length;
for(let i = 0; i<A.length; i++){
rightobj[A[i]] = (rightobj[A[i]] || 0) + 1;
}
let leftobj = {};
let leftLength = 0;
let leftLeader = 0;
let leftCount = 0;
for(let i = 0; i<A.length; i++){
rightobj[A[i]] -= 1;
rightLength -= 1;
leftobj[A[i]] = (leftobj[A[i]] || 0) + 1;
leftLength += 1;
if(leftobj[A[i]] > leftCount){
leftLeader = A[i];
leftCount = leftobj[A[i]];
}
if(rightobj[leftLeader] > parseInt(rightLength / 2) && leftCount > parseInt(leftLength / 2)) answer++
}
return answer
}최종결과
출처
