프로그래머스 Lv.1 달리기 경주 JS

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

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

 

위 문제를 풀이할 때, 이전 문제들이 stack을 이용해서 푸는 방식이어서 생각없이 배열로 풀기 시작했다.

 

function solution(players, callings) {
    var answer = [...players];
        for (let i = 0; i<callings.length; i++) {
            let calling = callings[i]
            let index = answer.indexOf(calling)
            
            if (index > 0) {
                // 배열에서 두 위치를 교환할 때 임시값이 필요함. 안전하게 변경하는 전형적 방법
                let temp = answer[index -1]
                answer[index -1] = calling
                answer[index] = temp
            }
        }
    return answer;
}

 

이 방식으로 문제를 해결했을 때, 코드 실행은 잘 됐지만 시간초과가 발생했다. players의 수가 늘어날수록 배열의 순서를 바꾸는 방식은 시간소모가 컸던 것이다. 그래서 다른 분의 풀이를 참고해서 hash 방식으로 풀이를 수정했다. 평소 자료구조를 시간들여 공부하지 않아서 이런 결과가 난 것이다. 이번 기회에 hash에 대해 정리해보고자 한다.

 

해시 테이블(Hash Table)은 key-value형태를 가지는 자료구조로, 배열과의 차이점이라고 한다면 배열은 key값이 숫자만 가능한데, 해시는 문자열도 가능하다. 해쉬함수를 이용해 입력값을 고정길이 문자열로 치환한다. 문자열로 받은 key 값을 해싱을 통해서 일정길이의 주소값으로 바꿔서 저장한다. 

 

1. 해시 테이블 : 해시함수를 사용해서 키를 해시값으로 매핑하고 이 해시값을 주소 또는 색인 삼아 데이터를 key-value로 저장한 묶음

2. map : key가 있는 데이터를 저장하는 데에 쓰이는 자료구조로, JS에서는 이를 hash에 활용하게 된다.

 

해시 테이블은 key-value가 1:1fh 매핑되어 있기 떄문에 시간 복잡도가 평균적으로 0(1)을 가지기 때문에 유리한 면이 있다.

 

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
}

 

 

해쉬 자료구조에 대해서는 잘 알지 못했지만, 다행히 프로젝트에서 Redis를 사용하면서 key-value의 사용법에 대해서는 어느정도 익숙해진 상태라 코드를 이해할 수 있었다. 해쉬 테이블은 O(N)의 시간 복잡도를 가지므로 시간초과일 때 적극적으로 활용할 수 있겠다는 생각이 들었다.