JavaScript로 배열에서 가장 자주 등장하는 단어 찾기

문제

영어 소문자 알파벳으로만 구성된 문자열 배열 arr을 첫 번째 인수로, 그리고 숫자 num(num은 배열 길이보다 작음)을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 배열 arr에서 가장 빈번하게 등장하는 상위 num개의 요소를 반환해야 합니다.

결괏값은 반드시 빈도가 높은 순서대로 정렬되어야 하며, 만약 두 단어의 등장 횟수가 같다면 사전순으로 앞에 오는 단어가 먼저 배치되어야 합니다.

예를 들어 함수의 입력이 다음과 같다고 가정해 보겠습니다.

입력

const arr = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"];
const num = 4;

출력

const output = ["the", "is", "sunny", "day"];

출력 설명

"the", "is", "sunny", "day"가 가장 많이 등장하는 네 단어이며, 각각 4회, 3회, 2회, 1회씩 나타났습니다.

풀이 코드

다음은 위 문제를 해결하는 코드입니다.

const arr = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"];
const num = 4;

const mostFrequent = (arr = [], num = 1) => {
    // 각 단어의 등장 횟수를 저장할 객체
    const map = {};
    let keys = [];

    // 1단계: 배열을 순회하며 단어별 빈도수 계산
    for (let i = 0; i < arr.length; i++) {
        if (map[arr[i]]) {
            map[arr[i]]++;
        } else {
            map[arr[i]] = 1;
        }
    }

    // 2단계: 고유 단어들을 keys 배열에 수집
    for (let i in map) {
        keys.push(i);
    }

    // 3단계: 빈도 내림차순 정렬, 빈도가 같으면 사전순 오름차순 정렬
    keys = keys.sort((a, b) => {
        if (map[a] === map[b]) {
            if (a > b) {
                return 1;
            } else {
                return -1;
            }
        }
        else {
            return map[b] - map[a];
        }
    })
    // 4단계: 상위 num개 요소만 잘라내기
    .slice(0, num);

    return keys;
};

console.log(mostFrequent(arr, num));

코드 동작 방식

이 풀이는 크게 세 단계로 진행됩니다.

1. 빈도수 계산: 일반 객체(map)를 해시 맵처럼 활용하여 배열을 한 번 순회하면서 각 단어의 등장 횟수를 기록합니다. 이미 존재하는 단어라면 값을 1 증가시키고, 처음 등장한 단어라면 1로 초기화합니다.

2. 정렬 조건 처리: sort() 메서드의 비교 함수에서 두 단어의 빈도수가 다르면 빈도가 높은 쪽이 앞에 오도록 하고(map[b] - map[a]), 빈도수가 같다면 문자열 비교를 통해 사전순으로 앞선 단어가 먼저 오도록 처리합니다.

3. 결과 추출: 정렬된 배열에 slice(0, num)을 적용하여 가장 빈번한 상위 num개의 단어만 최종적으로 반환합니다.

이 방식의 시간 복잡도는 빈도 계산에 O(n), 정렬에 O(k log k)(k는 고유 단어의 개수)가 소요되므로 전체적으로 O(n + k log k)입니다.

실행 결과

[ 'the', 'is', 'sunny', 'day' ]