[프로그래머스/Level1] 달리기 경주 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• HashMap → 시간 복잡도 : O(N)

 

1. players 배열을 돌며 Map에 player와 순서를 저장한다.

Map<String, Integer> map = new HashMap<>();
for(int i = 0 ; i < players.length ; i++) {
    map.put(players[i], i);
}

 

 

2. callings 배열을 돌며 경주를 진행한다.

  2-1) player 이름에 해당하는 순서를 찾는다.

int rank = map.get(player);

 

 

  2-2) 현재 player보다 한 칸 앞에 있는 사람을 찾고, 그 사람의 순위와 players 배열 값을 변경한다.

String frontPlayer = players[rank - 1];	// 현재 player보다 한 칸 앞에 있는 사람

map.replace(frontPlayer, rank);
players[rank] = frontPlayer;

 

 

  2-3) 현재 player의 순위도 한 칸 앞으로 변경하고, players 배열 값도 변경한다.

map.replace(player, rank -1);
players[rank -1] = player;

 

 

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public String[] solution(String[] players, String[] callings) {        
        
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0 ; i < players.length ; i++) {
            map.put(players[i], i);
        }
        
        for(String player : callings) {
            int rank = map.get(player);
            
            // 현재 player보다 한 칸 앞에 있는 사람 찾고, 그 사람 순위와 players 배열 값 변경하기
            String frontPlayer = players[rank - 1];
            
            map.replace(frontPlayer, rank);
            players[rank] = frontPlayer;
            
            // 현재 player의 순위도 한 칸 앞으로 변경하고, players 배열 값도 변경하기
            map.replace(player, rank -1);
            players[rank -1] = player;
        }
        
        return players;
    }
}
 

 

 

 

➕ 다른 풀이 방식

똑같은데 map의 등수와 playes에 있는 등수를 모두 변경할 때 코드 순서가 가독성이 좀 더 좋길래..ㅎㅎ

[JAVA] 달리기 경주

 

---

💦 어려웠던 점

- 그냥 완전탐색으로 매번 해당 call의 순서를 찾고, 앞 값과 값을 변경하도록 했었는데 시간 초과가 떴었다. (O(N^2))

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[연습문제][lv.1] 달리기 경주 - 자바(Java)