달리기 경주, Hash 자료구조

문제 설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

나의 문제 해결 방법

현재 선수들의 순위를 인덱스로 번호를 부여하고 불러진 이름을 현재 순위에서 인덱스 번호를 찾고, 앞 순서의 인덱스 (idx-1)와 위치를 배열의 길이만큼 반복해서 바꾼다.

 

const playerMap = {};
for (let i = 0; i < players.length; i++) {
    playerMap[players[i]] = i;
    }

플레이어 이름을 인덱스에 매핑하는 객체를 생성한다.

 

for (let i = 0; i < callings.length; i++) {
    const idx = playerMap[callings[i]];

    const temp = players[idx - 1];
    players[idx - 1] = callings[i];
    players[idx] = temp;

    playerMap[callings[i]] = idx - 1;
    playerMap[temp] = idx;
}

호출에 따라 플레이어들의 위치를 바꾼다. 호출된 플레이어의 현재 인덱스를 가져오고, 현재 인덱스의 왼쪽에 있는 플레이어와 위치를 바꾼다. playerMap을 업데이트하여 위치 변경을 반영한다.

 

다른 사람의 해결 방법

Hash 자료구조

Hashing

해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 해싱을 사용하여 데이터를 저장하는 자료구조를 해시 테이블(Hash Table)이라고 하며 이진탐색트리나 배열에 비해서 굉장히 빠른 속도로 탐색, 삽입, 삭제를 할 수 있다.

function solution(players, callings) {
    const hash = new Map();
    
    players.forEach((name, index) => {
        hash.set(name, index);
    })
    
    callings.forEach(name => {
        const currIdx = hash.get(name);
        const front = players[currIdx - 1];

        [players[currIdx], players[currIdx -1]] = [players[currIdx -1], players[currIdx]];
        
        hash.set(name, hash.get(name) - 1);
        hash.set(front, hash.get(name) + 1);
    })
    
    return players;
}