(JS) 동적 객체 key와 배열/객체 탐색 [Programmers - 달리기 경주]

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

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

문제를 풀기위해 아래와 같은 요소들을 고려하였다.

1. 탐색시간이 오래걸리지 않도록 키-값 쌍 구조인 객체를 사용하여 이름마다 직접 인덱싱 해준다.
2. 동적으로 객체를 생성(입력값에 따라)하고 사용하기 위해 대괄호를 활용한다.

function solution(players, callings) {
    const playerMap = {};

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

    for (let j=0; j<callings.length;j++) {
        let idx = playerMap[callings[j]];
        let temp = players[idx-1]; 

        players[idx-1] = callings[j];
        players[idx] = temp;

        playerMap[callings[j]] = idx-1;
        playerMap[temp] = idx;
    }
    
    return players;
}

 

 

• 객체의 동적인 이용

객체는 기본적으로 key - value의 형태로 자료를 저장한다. 이때 key값은 기본적으로 string 형식으로 저장이 된다.

이는 변수를 key값으로 사용하고 싶을때 문제가된다. 변수명을 넣어도 문자열로 저장이 되기 때문이다.

const obj = { 1: "one", true: "true" }; // "1", "true"로 저장된다.

var fruit = "apple";
const fruitObj = { fruit: "banana" } // fruit자리에 apple이 들어가지 않고 "fruit"로 저장된다.

숫자, boolean 등에 상관없이 key값은 모두 "1", "true", "fruit" 형태의 문자열로 저장된다.

 

객체의 key값을 동적으로 지정하는것 뿐만아니라 사용하기 위해서도 대괄호를 사용할 수 있다.

const obj = {};

// 키와 값을 동적으로 지정
const dynamicKey = 'age';
obj[dynamicKey] = 30;  // obj['age'] = 30 과 동일

console.log(obj[dynamicKey]);  // 출력: 30
console.log(obj.age);          // 출력: 30 (같은 결과)

 

 

• 탐색 시간복잡도

배열과 객체에서 특정 값을 찾아 사용하거나 위치를 변경하려면 여러가지 방법이 사용된다. 특히 A배열의 값을 기준으로 B배열의 값을 찾는 과정을 시행하려면 반복문 두개가 중첩되어 O(n²)의 시간복잡도를 가지게되어 탐색시간이 매우 오래 걸리게 된다.

 

시간을 줄이기 위해서는 배열과 객체의 탐색 형태를 알고 이용해야한다.

	배열	객체
O(1)	index로 탐색	key로 탐색
O(n)	값으로 탐색	값으로 탐색

 

A배열의 값을 기준으로 B배열의 값을 찾는 과정은 값으로 탐색 과정이 두번 중첩된것으로 O(n²)의 시간이 걸리게 된다.

 

여기서 배열값들을 객체의 key로 두고 value를 그 인덱스로 만들어주면 배열의 "값으로 탐색" 과정을 객체의 "key로 탐색"과정으로 만들어줄 수 있어 시간을 크게 절약할 수 있다.

 

function solution(players, callings) {
    const playerMap = {};

    // players 배열을 객체의 key-value 형태로 변환한다.
    for (let i = 0; i < players.length; i++) {
        playerMap[players[i]] = i;
    }

    // callings배열의 값을 순회하면서 객체의 key로 값을 찾으므로 반복문을 한개만 사용한다.
    for (let j=0; j<callings.length;j++) {
        let idx = playerMap[callings[j]];
        let temp = players[idx-1]; 

        players[idx-1] = callings[j];
        players[idx] = temp;

        playerMap[callings[j]] = idx-1;
        playerMap[temp] = idx;
    }
    
    return players;
}

 

callings 배열에 있는 값들을 하나씩 반복하며 playerMap 객체에 있는 값들을 찾을 수 있다. 객체 value에 index값을 직접 넣고 key값을 찾아 수정해주면서 배열에서 위치를 바꾸는(문제에서는 순위의 변동) 과정을 비슷하게 구현할 수 있다.