[알고리즘]-달리기 경주

요약

풀이 시간 : X (검색해서 찾아봄)

1차 풀이
1. 타임 아웃 발생, 배열 탐색, 시간복잡도 O(n)

2차 풀이
1. Map, Object => 해시테이블 기반 구조, 시간복잡도 O(1)

다른사람풀이
1. 배열의 구조 분해 할등을 통한 요소 교환

정리
1. 시간복잡도
2. 직관적인 변수명 사용
3. 배열의 구조 분해 할당을 통한 요소 교환

문제 링크

[프로그래머스]-달리기 경주

1차 풀이

function solution(players, callings) {    
    for(const [idx, call] of callings.entries()){
        const caller = players.indexOf(call);
        const passer = caller - 1;
        if(passer >= 0){
            const temp = players[passer];
            players[passer] = players[caller];
            players[caller] = temp;
        }
    }
    return players;
}

2차 풀이

function solution(players, callings) {
    // 검색을 위한 이름-인덱스 매핑 맵
    const mapRank = new Map(players.map((player, idx)=> [player, idx]));
    
    for(const [idx, call] of callings.entries()){
        const callerIdx = mapRank.get(call); // 호출된 선수 인덱스
        const passerIdx = callerIdx - 1; // 앞 순위 선수 인덱스
      	const shouldChangeRank = passerIdx >= 0; 
      
        if(shouldChangeRank){ // 순위 변경이 가능한 경우
            // 순위 반영
            const passerName = players[passerIdx];
            players[passerIdx] = players[callerIdx];
            players[callerIdx] = passerName;
            
            // 맵 인덱스 업데이트
            mapRank.set(call, passerIdx);
            mapRank.set(passerName, callerIdx);
        }
    }
    
    return players;
}

다른 사람 풀이 정리

function solution(players, callings) {
    // 검색을 위한 이름-인덱스 매핑 맵 초기화
    const mapRank = new Map(players.map((player, idx)=> [player, idx]));
    
    for(const [idx, call] of callings.entries()){
        const callerIdx = mapRank.get(call); // 호출된 선수 인덱스
        const passerIdx = callerIdx - 1; // 앞 순위 선수 인덱스
        if(passerIdx >= 0){
            // 순위 반영, 구조 분해 할당을 활용한 요소 교환
            [players[passerIdx], players[callerIdx]] = [players[callerIdx], players[passerIdx]];
            
            // 맵 인덱스 업데이트
            mapRank.set(call, passerIdx);
            mapRank.set(passerName, callerIdx);
        }
    }
    
    return players;
}