JavaScript에서의 Map 객체 활용: 데이터 매핑과 효율적인 검색

프로그래머스에서 코딩테스트를 진행하다가 시간초과가 나왔다.

먼저 문제에서 배열을 순회해야했었고 for문을 통해서 작성하고 for문 안에서 indexOf를 순회했다.

배열의 길이가 길어질수록 각 호출마다 indexOf를 연산하게 되면서 O(n)의 시간복잡도를 가지게 된다.

 

문제를 풀다가 Map객체를 활용하는 방법이 효율적이게 작용하는걸 알게 되었다.

 

 

문제설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다. 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

입출력 예

players	callings	result
["mumu", "soe", "poe", "kai", "mine"]	["kai", "kai", "mine", "mine"]	["mumu", "kai", "mine", "soe", "poe"]

 

처음 작성한 코드

function solution(players, callings) {
    var answer = players;
    for(let i = 0; i < callings.length; i++) {
        const index = answer.indexOf(callings[i])
        const temp = answer[index]
        answer[index] = answer[index-1]
        answer[index-1] =temp
        
        }
    return answer;
}

- 이름이 불리는 index를 찾고 해당 배열에 앞에 있는 이름과 불러진 이름이 적용되도록 했다.

- 이렇게 하니 해당 for문 내부에서도 length마다 indexOf를 순회해야하다보니 시간초과가 되었다.

 

그래서 수정한 코드

function solution(players, callings) {
    const playerIndices = new Map();
    for(let i = 0; i < players.length; i++) {
        playerIndices.set(players[i], i);
    }
    
    for(let calling of callings) {
        const index = playerIndices.get(calling);
        if(index > 0){
            [players[index], players[index-1]] = [players[index-1], players[index]];
            playerIndices.set(players[index], index);
            playerIndices.set(players[index-1], index - 1);
        }
    }

    return players;
}

- 새로운 Map 객체를 생성하고 선수들의 이름과 위치한 index정보를 먼저 저장해주었다. 처음 작성한 코드처럼 for문 내부에서 순회하는게 아니기 때문에 더 빠르게 index정보에 접근할 수 있다.

- for문에서는 for of문을 통해서 해당하는 index를 찾고 배열의 해당하는 요소 앞, 뒤를 변경하도록 해주었다.

- 그리고 변경된 위치를 playerIndices 배열에도 같이 변경되도록 했다.

 

---

 

const playerIndices = players.map((item, i) => [item, i]);

여기서 처음에는 new Map을 그냥 map함수로 index를 같이 매핑해도 되지않을까 했지만 new Map 객체를 생성하여 사용하는것과 차이점이 있었다.

 

 

 

new Map과 map 메서드의 차이점

- 검색 속도: Map 객체는 내부적으로 해시 맵 구조를 사용하기 때문에 빠른 검색 속도를 제공한다. 반면 map메서드를 사용하게 되면 검색시 선형 탐색을 수행하기 때문에 상대적으로 느릴 수 있다.

- 중복된 이름: 혹시모를 중복된 이름이 있을 수 있다. new Map 객체는 key가 유일해야 하지만 map 메서드는 중복된 선수 이름 까지도 모두 배열로 생성하기 때문에 중복 처리가 필요할 수 있다.

- 순서 보장: ES6부터 도입된 Map 객체는 요소들이 추가된 순서대로 반복된다. 그렇기 때문에 입력한 순서대로 데이터가 유지되어 정확한 결과를 얻을 수 있다.