[프로그래머스 lv.1] 달리기 경주 (JS)

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

프로그래머스

 

문제 설명과 입출력이 직관적으로 다가와서 쉬운 편이라고 생각했으나..

객체와 배열의 특징에 대해 다시 한 번 생각을 정리할 수 있는 문제였다!

 

 

문제

 

 

첫 시도 (오답)

callings.forEach(player => {
  let curRank = players.indexOf(player);
  let tmp = players[curRank - 1];
  players[curRank - 1] = player;
  players[curRank] = tmp;
});

return players;

 

indexOf를 활용해 이름이 불린 선수의 현재 등수를 찾고, 앞뒤 요소(선수)를 바꿔줬다.

간단하게 풀릴 줄 알았으나 4가지 케이스에서 시간초과가 떴다.

indexOf로 배열의 앞에서부터 선수를 찾는 과정이 반복되고, 이 동작은 탐색하는 배열이 길어질수록 + 여러번 탐색할수록 시간을 많이 소요하는 것이 문제겠구나 생각했다.

 

 

재도전 (정답)

let rank_of_players = {};
let player_of_rank = {};
    
players.forEach((player, rank) => {
   rank_of_players[player] = rank;
    player_of_rank[rank] = player;
});
    
callings.forEach(player => {
   let cur_rank = rank_of_players[player];
    let ahead_player = player_of_rank[cur_rank - 1];
    
    rank_of_players[player] = cur_rank - 1;
    rank_of_players[ahead_player] = cur_rank;
    
    player_of_rank[cur_rank] = ahead_player;
    player_of_rank[cur_rank - 1] = player;
});
    
let sort_arr = Object.entries(rank_of_players).sort(([,a], [,b]) => a - b);
let answer = sort_arr.map(([player, _]) => {
   return player; 
});
    
return answer;

 

순서대로 선수의 이름이 있는지 확인하는 방법이 아닌, 선수의 이름으로 바로 등수를 확인할 수 있는 방법을 생각했다.

바로 key-value 쌍으로 구성된 객체를 이용하자 생각이 들었다.

그런데 {player: rank} 구조라면 이름이 불린 선수의 앞에 달리고있는 선수를 찾을 때 value를 갖고있는 key를 찾아야할텐데.. 그럼 결국 앞에서부터 차례차례 value를 확인하는 수밖에 없지않나..? 그럼 indexOf를 사용하는 거랑 같은 결과 아닌가? 하는 고민이 들었다.

이 때부터 약간 함정에 빠지긴했지만.. rank로 바로 player를 찾을 수 있도록 {rank: player} 구조의 객체를 하나 더 만들어서 관리하기로 했다.

 

두 객체를 기반으로 이름이 불리는 선수와 앞에 달리던 선수의 등수를 바꿔주고, 각 랭킹에 해당하는 선수들의 이름도 업데이트 해줬다.

객체는 sort를 지원하지 않기에, [key, value] 형태의 배열이 담긴 배열로 만들어주고 두번째 원소인 value를 기준으로 정렬해주었다.

그 후 첫번째 원소인 선수의 이름만 따로 배열로 만들어 반환했다.

 

그런데 비교적 간단한 문제에 너무 많은 과정과 여러번의 배열 생성이 있다는 것이 효율적이진 않은 것 같다는 생각이 들었다.

제출 후 객체를 사용해 풀이한 사람들의 풀이를 더 살펴보았다.

 

 

재도전2 (정답)

let rank_of_players = {};
players.forEach((player, rank) => {
   rank_of_players[player] = rank;
});

callings.forEach(player => {
   // 객체 업데이트
    let prev_rank = rank_of_players[player];
    rank_of_players[player] = prev_rank - 1;
    let ahead_player = players[prev_rank -1];
    rank_of_players[ahead_player] = prev_rank;
    
    // 배열 업데이트
    players[prev_rank] = ahead_player;
    players[prev_rank - 1] = player;
});

return players;

ㅎㅎㅎ 다른 사람들의 코드를 보다가 깨달았다.

내가 따로 만들어주지 않아도 이미 숫자로 빠르게 이름을 알아낼 수 있는 자료구조가 있다는 것을..

심지어 그건 정렬해주지 않아도 이미 빠른 순서대로 정렬이 되어있다는 것을..

 

위의 코드와 유사하지만 정리해보자면

1) 이름이 불린 선수의 등수를 빠르게 찾을 수 있도록 rank_of_players 객체 생성 ({선수 이름: 등수} 구조)

→ 각 등수에 해당하는 선수를 알기위한 객체는 만들 필요가 없다. 이미 players 배열에 순서대로 저장돼있기 때문에

 

2) 이름이 불린 선수의 등수를 저장해두고, 한단계 앞 등수로 바꿔주기

 

3) 이름이 불린 선수의 앞에서 달리고있던 선수를 players 배열에서 인덱스를 활용해 가져오기

 

4) 불러온 선수의 등수를 바꿔주기 (rank_of_players 객체)

 

5) 배열에서도 이름불린 선수 ↔ 앞에 달리던 선수 순서 바꿔주기

 

 

기억해둘 것

나는 어떤 값을 찾기위해서 이런 값을 사용할 수 있는데 그럼 어떤 형태로 데이터를 관리하는게 효율적일까? 생각해보는 것이 필요한 것 같다.

객체 (key-value): 문자열로 인덱스를 찾기위해 반복문을 사용하는 대신 바로 접근할 수 있는 객체를 사용함

배열: 인덱스에 해당하는 값을 찾기위해 사용함 순서대로 정렬되어있고, n번째에 해당하는 값이 무엇인지 찾을 때는 배열을 활용하자