Codility Lesson8 - Dominator

🔍 문제

---

주어진 배열 A에서 과반수 이상으로 같은 값을 가진 인덱스들을 찾아서 아무 인덱스나 return 해주면 되는 문제이다.

Dominator coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

처음에 문제를 잘못 읽고 과반수 이상으로 같은 값을 가진 인덱스들을 모두 배열로 반환하는 건 줄 알았다가 오류떠서 다시 읽어보니 index중 아무 값이나 반환하면 되는 문제였다. Map을 이용해서 풀었으며, 시간 복잡도는 O(N*log(N)) or O(N)가 나왔다.

function solution(A) {
    if (A.length === 0) return -1;

    let map = new Map();
    const moreThanHalf = parseInt(A.length/2) + 1;

    for(let i = 0; i < A.length; i++) {
        let keyVal = A[i];
        if(map.has(keyVal)) {
            map.get(keyVal).push(i);
        } else {
            let valArr = [i];
            map.set(keyVal, valArr);
        }
    }

    for(let value of map.values()) {
        if(value.length >= moreThanHalf) return value[0];
    }

    return -1;
}

참고로, 자바스트립트에서 Map과 Object의 차이점은 다음과 같다. 자세한 내용은 아래 링크로 가면 볼 수 있다
자세한내용 링크 👉 MDN web docs : Map - JavaScript

👀 Map과 Object의 비교

Map 객체는 요소의 삽입 순서대로 원소를 순회합니다. for...of 반복문은 각 순회에서 [key, value]로 이루어진 배열을 반환합니다.
Object는 값에 키를 할당할 수 있고, 그 키로 값을 얻을 수 있고, 키를 삭제할 수 있으며 어떤 키에 값이 존재하는지 확인할 수 있다는 점에서 Maps와 유사합니다. 이러한 이유와, 내장 대체제가 없었기 때문에 역사적으로 Object를 Map 대신 사용하곤 했습니다. 그러나 어떤 상황에선 Map을 고려해야 할 몇 가지 중요한 차이점이 있습니다.

 

• Object의 키에는 String과 Symbol을 사용할 수 있지만, Map은 함수, 객체, 원시 자료형 등 어떤 값도 사용할 수 있습니다.
• Map의 키는 삽입순으로 정렬되지만 Object의 키는 그렇지 않습니다. 따라서 Map을 순회하면 키를 삽입한 순서대로 반환합니다.
• Map의 크기는 size 속성으로 쉽게 얻을 수 있지만 Object의 속성 수는 직접 판별해야 합니다.
• Map은 바로 순회할 수 있지만, Object를 순회하려면 어떤 방법이든 키의 배열을 얻고, 그 배열을 순회해야 합니다.
• Object는 프로토타입을 가지므로, 주의하지 않으면 키가 충돌할 수 있습니다. ES5부터는 Object.create(null)을 사용해도 되지만 거의 쓰이지 않습니다.
• 잦은 키의 추가와 제거가 필요한 시나리오에서는 Map이 더 빠릅니다.