프로그래머스_LV1_달리기 경주(풀이 및 시간초과 해결하기)

오랜만에 돌아온 JAVA 알고리즘 문제풀이
갑자기 JAVA를 하는 이유는 사내 알고리즘대회에
어쩌다 보니 나가게 되어서 강제로 공부를 시작하게 되었다...
작년에 이직한 이후로 처음이니까 거의 1년 만에 해보니까 
LV1도 쉽지않ㄷ ㅏ......⭐️ 나 이렇게 못했었나....

출처:프로그래머스

👉 문제 링크

프로그래머스

간단하게 문제를 설명하면 players 배열을 순서를 재배치하는데 callings 배열에서 불린 이름이 players 배열에서 앞뒤로 순서가 바뀌게 정렬하면 된다.

1. 순수 배열로만 풀기

public static String[] Arraysolution(String[] players, String[] callings) {
        String[] answer = players;

        for(int i=0; i< callings.length ; i++) {
            String tempCallingName = callings[i];
            for (int j = 0; j < players.length; j++) {
                if (players[j].equals(tempCallingName) && j != 0) {
                    String tempPrePlayerName = players[j - 1];
                    answer[j - 1] = tempCallingName;
                    answer[j] = tempPrePlayerName;
                    break;
                }
            }
        }
        return answer;
    }

솔직히 오랜만에 풀면서 이 정도면 아주 기깔나게 풀었다고 생각했다
답도 맞았고..그러나 느리면 큰일 나는 한국사회에서 이 코드는 실패했다.
for문 하나당 O(n)의 시간복잡도를 갖는다.
따라서 내가 짠 이중 for문의 경우 O(n) * O(n) 만큼의 시간복잡도를 갖게 되니까, O(n^2)가 되고 
배열개수만큼 다 돌게 되니까 데이터 양이 늘어나면 느려질 수밖에 없다.

2. ArrayList 로 풀기

 public static String[] Listsolution(String[] players, String[] callings) {
        String[] answer = {};

        List<String> playersList = new ArrayList<String>(Arrays.asList(players));
        List<String> callingList = new ArrayList<String>(Arrays.asList(callings));
        List<String> answerList = playersList;

        for(int i=0; i< callingList.size() ; i++)
        {
           int playerNum = answerList.indexOf(callingList.get(i));
           if(playerNum != 0) {
               String tempStr = playersList.get(playerNum-1);
               answerList.set(playerNum-1, playersList.get(playerNum));
               answerList.set(playerNum, tempStr);
           }
        }
        answer = (String[]) answerList.toArray(new String[answerList.size()]);

        return answer;
    }

이거 짯을때 아주 잘했다고 생각했는데..!!!!!!!
ArrayList를 사용해서 for문 하나로 줄였지만 ArrayList의 indexOf는 매개변수로 Object를 받아 Object의 위치와 포함 여부를 리턴하므로, 배열 전체를 순회하는 작업이 필요해서 O(N)의 시간복잡도를 가지게 되는데 알고리즘 세상에서는 받아줄 수 없어서 실패
 

3. HashMap으로 풀기

public static String[] Hashsolution(String[] players, String[] callings) {
        String[] answer = players;
        HashMap<String, Integer> playerMap = new HashMap<String, Integer>();

        for(int i=0;i< players.length;i++)
            playerMap.put(players[i],i);

        for(String calling : callings)
        {
            int count = playerMap.get(calling);
            String prePlayer = answer[count-1];
            answer[count-1] = calling;
            answer[count] = prePlayer;
            playerMap.put(calling,count-1);
            playerMap.put(prePlayer,count);
        }

        return answer;
    }

조금 어이가 없지만 이게 통과가 되더라!!!!!!
그래서 찾아보니까 HashMap은 키-값으로 매핑돼서 특정요소를 찾는 검색의 성능이 빠르다는 장점이 있다.
시간복잡도도 contain, put, get이 O(1)이어서 이게 훨씬 빠르고 맞는 답이었다.
 
👉 시간복잡도 정리
ArrayList

add	O(1)
remove	O(n)
get	O(1)
Contains	O(n)

특징 : 데이터 추가, 삭제 시 임시 배열을 생성해서 데이터를 복사하므로 대량의 자료를 추가 삭제할 경우 성능이 느림
HashMap

get	O(1)
containsKey	O(1)
next	O(h/n)

특징 : 순서에 상관없이 저장되고 키-값 형태를 가져서 검색이 빠름