Question

시간복잡도에 걸렸네요

    for (int i = 0; i < callings.length; i++) {
        for (int j = 1; j < player.length; j++) {
            if(callings[i].equals(player[j])){
                String david = player[j];
                player[j] = player [j-1];
                player[j-1] = david;
            }
        }
    }

이렇게 2가지 방법을 생각했는데.. 시간복잡도에 걸린거같아요..

작성중인 코드―Solution.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        for(String calling : callings) {
           for (int i = 1; i < players.length; i++) {
               if(players[i].equals(calling)){
                String temp = players[i];
                players[i] = players[i-1];
                players[i-1] = temp;
                break;
               }
           }
       }
        return players;
    }
}

Answer 1

player가 최대 50000명까지 있을 수 있습니다.
50000명이 참가한 경기에서 꼴등이 앞사람을 추월한다고 하면 6번째 줄에 있는 반복문에 의해서 50000번 탐색 끝에 players[i].equals(calling)에 해당 되는 선수를 찾게 됩니다.
calling의 길이가 최대 1,000,000이기 때문에 이런 worst case가 계속 반복될 경우 최대 50,000 * 1,000,000번을 반복하게 됩니다.
호명된 사람의 index를 한 번에 찾을 수 있으면 좋을 것 같습니다.
map이라는 자료구조를 활용해서 한 번에 그 사람의 index를 찾을 수 있으면 시간 단축에 도움이 될 거에요!
key = name
value = index

한***

2023.5.30 15:17

시간복잡도에 걸렸네요

작성중인 코드―Solution.java

1 개의 답변

김***

2023.5.30 15:47

답변 쓰기

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