Question

(JAVA) Collections.swap 사용하면 효율성 에러.. (풀이 있음)

1단계라서 Swap을 써도 풀릴줄 알았는데 아니더라군요

swap은 확실히 시간복잡도가 O(n)이 걸렷습니다.

어쩔수없이 자작으로 효율성있는 Swap을 구현해야했습니다.

그래서 Map으로 구현하려고했는데,

이게 Key: 이름 , Value: 랭크순위 로 맵을 하나 쓰고 풀다가보니,

해설자가 외친 추월한 이름을 기준으로 추월한 사람의 랭크순위는 알겠는데,

추월당한 사람을 모릅니다. 추월당한사람은 추월한 사람의 랭크순위-1인데
이걸 구하려면 Map을 한바퀴 순차탐색해야합니다. (O(N)) 발생

그래서 Key: 랭크순위, Value: 이름으로 맵을 하나 더 작성했습니다.

이러면 추월당한 사람의 이름을 랭크순위로 판단이 (O(1))로 가능해집니다.

그 후, 2개의 맵을 갱신해주면 로직 끝

작성중인 코드―Solution.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;
class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];

        Map<Integer,String> map = new TreeMap<>();
        Map<String,Integer> map2 = new HashMap<>();

        for(int i=0;i<players.length;i++){
            map.put(i+1,players[i]);
            map2.put(players[i],i+1);
        }

        for(int i=0;i<callings.length;i++){

            //추월한 선수
            String call = callings[i];

            int idx =map2.get(call);

            //뒤처진 선수
            String a = map.get(idx-1);

            //map2  갱신
            map2.put(call,idx-1);
            map2.put(a,idx);

            //map1 갱신
            map.put(idx-1,call);
            map.put(idx,a);

        }

        int idx=0;
        for(int key:map.keySet()){
            answer[idx++]=map.get(key);
        }



        return answer;
    }
}

김***

2023.4.7 16:12

(JAVA) Collections.swap 사용하면 효율성 에러.. (풀이 있음)

작성중인 코드―Solution.java

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.