#24😂 달리기 경주 / indexOf는 시간복잡도가 많이 든다!

[문제]

출처 : https://school.programmers.co.kr

출처 : https://school.programmers.co.kr

---

[해설]

- 갖가지 방법을 써봐도 계속 시간 초과가 나왔다.

- 즉, 문제 해결 방법 자체가 틀린건 아닌데 리소스를 너무 많이 사용하는 코드라는 의미이다.

- 아래는 내가 문제를 풀기 위해 작성한 코드이다.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public String[] solution(String[] players, String[] callings) { 
        List<String> players_list = new ArrayList(Arrays.asList(players));

        for(int k = 0; k < callings.length; k++) {
            // 해설진이 호명한 선수
            String man = callings[k];
            
            // 현재 호명된 선수의 위치
            int index = players_list.indexOf(man);
            
            // 추월 당한 선수
            String passed = players_list.get(index - 1);
            players_list.remove(man);
            players_list.add(index - 1, man);
        }
        
        String[] answer = players_list.stream().toArray(String[]::new);
        return answer;
    }
}

- 풀이를 참고해 보기전에 다른 사람들이 작성해 놓은 일종의 힌트를 참고해 보았다.

- 그 중 indexOf는 리소스가 많이 드니 map을 이용해 보라는 내용을 보았다.

- 아래는 내가 참고한 힌트이다.

 

1. JS로 풀이한 내용이지만 답변 내용 자체가 좋았다.

출처 : https://school.programmers.co.kr/questions/47264

2. JAVA 풀이 힌트1

출처 : https://school.programmers.co.kr/questions/47150

3. JAVA 풀이 힌트2

출처 : https://school.programmers.co.kr/questions/47069

 

- 이번 문제의 가장 큰 수확은 indexOf 대신에 map을 사용하여 시간복잡도를 줄일 수 있다는 개념을 내 머리에 심었다는 것이다.

import java.util.Map;
import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        // 선수들의 등수를 담을 map
        Map<String, Integer> players_map = new HashMap<String, Integer>();
        for(int i = 0; i < players.length; i++) players_map.put(players[i], i);
        
        for(int k = 0; k < callings.length; k++) {
            // 현재 호명된 선수의 등수
            int index = players_map.get(callings[k]);
            
            // 호명된 선수와 앞 선수 위치 변경
            String tmp = players[index - 1];
            players[index - 1] = players[index];
            players[index] = tmp;
            
            // 선수들의 등수 정보 변경
            players_map.put(callings[k], index - 1);
            players_map.put(tmp, index);
        }
        return players;
    }
}

통과!