[Javascript] Codility Lesson 8 - Dominator

 

문제: https://app.codility.com/programmers/lessons/8-leader/dominator/

 

문제 요약:

• N개의 정수로 이루어진 배열 A가 주어진다.
• N의 범위는 0 ~ 100,000이다.
• 배열 A의 각 요소의 범위는 -2,147,483,648 ~ 2,147,483,648이다.
• 배열 A에서 절반 이상을 차지하는 정수(dominator)의 인덱스 중 하나를 반환하여라. 
• 배열 A에서 절반 이상을 차지하는 정수가 없다면 -1을 반환한다.

 

시도 1: 

function solution(A) {
    let stack = [];

    for (let i = 0; i < A.length; i++) {
    	// stack에 순서대로 정수를 넣고
        stack.push(A[i]);
        
        // 2개 이상의 정수가 stack에 들어갔을 때
        if (stack.length > 1) {
            let len = stack.length;
            // 맨 끝 정수와 맨 끝에서 두 번째 정수를 비교하여 다르면 stack에서 제거.
            if (stack[len - 1] !== stack[len - 2]) {
                stack.pop();
                stack.pop();
            };
        };
    };

    // stack에 남아있는 숫자가 절반 이상을 차지하는 숫자라 판단하고 인덱스를 구하여 반환한다.
    let result = stack[0] ? A.indexOf(stack[0]) : -1;
    return result;
}

https://app.codility.com/

stack에 순서대로 정수를 적재하다가 2개 이상의 정수가 stack에 쌓이면 제일 최근에 stack에 들어간 정수와 그 직전에 들어간 정수를 비교한다. 비교한 값이 상이하면 두 개 정수를 모두 stack에서 제거하고, 값이 동일하다면 그대로 유지한 채 다음 정수를 stack에 넣는다. 이 과정을 반복하다 보면, 서로 다른 값들은 stack에서 제거될 것이고 마지막에는 이러한 비교에서 살아남은 정수가 남게 될 것이라고 생각했다. 하지만 몇 가지 테스트 케이스를 작성하며 허점이 있다는 걸 알게 됐다. 

[1,1,1,1,2,2,3,3] → dominator는 1이기 때문에 result는 0 or 1 or 2 or 3 이어야 된다. 하지만 위 방법으로 풀었을 때 result는 -1이다. 

[1,2,3,4,5] → dominator가 없기 때문에 result는 -1 이어야 된다. 하지만 위 방법으로 풀었을 때 result는 4이다.

 

 

시도 2:

function solution(A) {
    let value = null;
    let nCnt = {};

    for (let i = 0; i < A.length; i++) {
        nCnt[A[i]] =  nCnt[A[i]] ? nCnt[A[i]] + 1 : 1;
        
        if (nCnt[A[i]] > A.length / 2) {
            value = A[i];
        }
    };

    let result = value !== null ? A.indexOf(value) : -1;
    return result; 
}

https://app.codility.com/

결국 객체 타입을 활용하여 해결했다. 배열 A를 순회하며 key값에는 배열 A의 요소, value값에는 요소의 개수를 카운팅 한 값을 넣었고, value값이 배열 A의 길이 절반 이상이 되면 대응하는 key값이 dominator이기 때문에 해당 값의 인덱스 위치를 반환하면 된다.