[알고리즘 Lv.1] 달리기 경주(HashMap을 아니?, 깊은 복사)

초기 달리기 선수 순서 [철수, 유리, 짱구, 맹구, 훈이]

 

선수가 호명되면 앞 순서 선수를 추월한 것이다.

 

예) 호명 : [맹구, 맹구, 훈이]  ➡ 순서 : [철수, 맹구, 유리, 훈이, 짱구]

 

이처럼 바뀐 순서의 배열을 반환할 것.

 

정답

import java.util.Arrays;
import java.util.HashMap;
 
class Solution {
    public String[] solution(String[] players, String[] callings) {
        // players 배열의 복사본을 만들어 answer 배열에 대입합니다. 깊은 복사
        String[] answer = Arrays.copyOf(players, players.length);
       // -> 얕은 복사: String[] answer = players
        // HashMap을 만들어 각 플레이어의 인덱스를 저장합니다.
        HashMap<String, Integer> playerMap = new HashMap<>();
        for (int i = 0; i < players.length; i++) {
            playerMap.put(players[i], i);
        }
        
        // callings 배열을 반복하면서 각 calling의 인덱스를 찾아서 스왑합니다.
        for (String calling : callings) {
            int index = playerMap.get(calling);
            if (index >= 1) {
                swap(answer, index, index-1);  // 인덱스 index와 index-1의 요소를 스왑합니다.
                playerMap.put(answer[index], index);  // answer[index]의 인덱스를 업데이트합니다.
                playerMap.put(answer[index-1], index-1);  // answer[index-1]의 인덱스를 업데이트합니다.
            }
        }
        
        return answer;
    }
    
    // 배열의 두 요소를 교환하는 swap 메서드입니다.
    private void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

처음에는 이중 for문을 사용하여 해결하려 했지만, 데이터의 갯수에 따라 실행시간이 어마어마하게 증가하였다.

또한 얕은 복사(String[] answer = players)를 하여 answer가 바뀌면 players가 바뀌는 문제가 있었다.

 

이를 해결하려면 HashMap을 사용하여야 한다.

깊은 복사를 하여 원본 데이터와 새로운 데이터가 독립적으로 변하도록 한다.

String[] answer = Arrays.copyOf(players, players.length);

 

참고: https://kimeuncheol.tistory.com/98

java :) 얕은복사와 깊은복사, Arrays.copyOf()와 Arrays.copeOfRange() 사용방법

 

HashMap

HashMap은 Java의 Collection Framework 중 하나로, key-value 쌍으로 데이터를 저장하는 자료구조입니다.

HashMap은 내부적으로 hash function을 사용하여 key와 value를 연결합니다. 이를 통해 매우 빠른 검색 속도를 제공하므로, 많은 양의 데이터를 빠르게 검색해야 하는 경우에 유용합니다.

HashMap의 가장 큰 장점은 key를 사용하여 데이터를 검색할 때 빠른 속도를 보장한다는 것입니다. 이를 위해 HashMap은 데이터를 저장할 때 각 데이터의 key 값을 해시 함수에 입력하여 인덱스를 계산합니다. 따라서 검색 시에도 같은 해시 함수를 이용하여 빠르게 검색이 가능합니다.

HashMap은 다음과 같은 특징을 가집니다.

• 순서가 없습니다.
• key와 value는 null이 될 수 있습니다.
• 동기화를 지원하지 않으므로, 멀티스레드 환경에서 안전하게 사용하려면 ConcurrentHashMap 등의 클래스를 사용해야 합니다.
• HashMap은 매우 높은 성능을 가지므로, 검색이 많이 필요한 경우에는 ArrayList 등의 다른 자료구조보다 우수한 성능을 보입니다. 하지만 key에 대한 순서를 유지하려면 LinkedHashMap을 사용해야 하며, 멀티스레드 환경에서는 ConcurrentHashMap 등을 사용해야 합니다.