[TIL] (230817) Map은 key값을 활용한 value의 검색 속도가 빠르다.(시간 복잡도 주의)

 

 

프로그래머스 문제를 풀던 중 답은 맞으나 문제 제출하기를 진행했을때 일정구간에서 계속 런타임 오류가 발생했다.
나는 아무리 생각해도 뭐가 문제인지 모르겠어서 내 코드와 예시코드를 비교하면서 하나씩 살펴보았다. 

 

---

🔸문제점

프로그래머스-달리기경주

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

 

 

 

나는 이 문제를 보고  callings 배열의 순서대로 players 배열에서 인덱스값을 찾고

찾은 인덱스를 기준으로 앞의 인덱스값과 변경하면 될 것이라고 생각했다.

그리고 아래와 같이 코딩을 했다.

 

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        ArrayList<String> playerList = new ArrayList<>();
        Collections.addAll(playerList, players); // players 배열을 ArrayList로 복사
        
        for (String calling : callings) {
            int temp = playerList.indexOf(calling);
            Collections.swap(playerList, temp - 1, temp);
        }
        String[] playerArray = playerList.toArray(new String[0]);
        return playerArray;
    }
}

 

 

결과는~~

 

 

런타임 오류로 실패했다^^

---

 

🔸시도해본 것들 

 

1. 시험에서는 반환값이 String[]로 되어있어서 마지막에  ArrayList<String> -> String[]가 속도에 영향을 주지 않을까?

그래서 임의로 반환값을 변경해봤다.

 

 

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public ArrayList<String> solution(String[] players, String[] callings) {
        ArrayList<String> playerList = new ArrayList<>();
        Collections.addAll(playerList, players); // players 배열을 ArrayList로 복사
        
        for (String calling : callings) {
            int temp = playerList.indexOf(calling);
            Collections.swap(playerList, temp - 1, temp);
        }
        // String[] playerArray = playerList.toArray(new String[0]);
        return playerList;
    }
}

 

결과는 동일하게 런타임 오류!!

실행된 항목도 이전과 비슷한 처리속도를 보였다.

그렇다는건 이 코드 자체가 문제겠지.....

 

 

 

 

확인해보니 내가 한 코딩은 아래와 같은 문제가 있다.

 

선수 수가 n, 호출 수가 m인 경우 O(n * m)의 시간 복잡도를 가집니다. 

 

 

 

발생한 시간복잡도를 좀 더 자세하게 확인해보았다.

 

indexOf(): 이 작업은 playerList에서 특정 값을 찾는 것입니다. 최악의 경우, 리스트 내의 모든 요소를 검사해야 하므로 O(n)의 시간이 걸립니다. 여기서 n은 playerList의 길이입니다.

Collections.swap(): 이 작업은 두 개의 요소를 스왑하는 것입니다. 이 작업은 O(1)의 시간 복잡도를 가집니다. 하지만 여기서의 스왑은 indexOf()를 통해 찾은 인덱스와 그 앞의 인덱스를 스왑하는데, indexOf() 자체가 O(n)이므로 이 연산도 결국 O(n) 시간이 걸립니다.

따라서, callings 배열의 길이가 m이고, playerList의 길이가 n일 때, callings 배열의 각 요소를 처리하면서 indexOf()와 Collections.swap()이 실행되기 때문에 전체적인 시간 복잡도는 O(n * m)이 됩니다.

indexOf()과 swap으로 O(n * m)의 시간 복잡도가 증가하기 때문에 정답은 맞지만 런타임 오류로 제출이 안되는 것이었다.

 

 

🤔 그럼 어떤식으로 코드를 짜야할까?

 

🙋‍♀ Key 를 기반으로 Value를 검색할 수 있어서 검색 속도가 상대적으로 빠른 Map을 사용해보자.

 

import java.util.HashMap;

public class Solution {
    public String[] solution(String[] players, String[] callings) {
        int n = players.length;
        HashMap<String, Integer> indexMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            indexMap.put(players[i], i);
        }

        for (String calling : callings) {
            int idx = indexMap.get(calling);
            if (idx > 0) {
                String temp = players[idx - 1];
                players[idx - 1] = players[idx];
                players[idx] = temp;

                indexMap.put(players[idx - 1], idx - 1);
                indexMap.put(players[idx], idx);
            }
        }
        return players;
    }
}

 

HashMap을 사용한다면 (1). key값 중복불가, (2) key값으로 검색시 속도 향상 이라는 장점이 있다.

이 코드에서는 String[] players의 요소값을 key로, 인덱스와 매칭되는 i값을 value로 사용한다.

그리고 temp를 이용하여 해당되는 idx와 idx-1의 위치를 바꿀 수 있도록 코딩한다.

= 제출 성공

 

 

 

---

 

🔸해결

Map의 key, value값을 이용하여 빠른 탐색을 진행했다.

temp를 사용하여 바꿀 인덱스의 값을 설정하고 index.put으로 바뀐 인덱스 번호까지 함께 재설정해줬다.

 

 

 

---

 

🔸알게 된 점 

Collections.swap()와 indexOf()는 내가 원하는데로 동작하는 메서드가 맞지만, 이 두가지가 함께 동작할때 시간복잡도가 n*m일 정도로 많이 상승한다는것은 몰랐다.

시간 복잡도(Time Complexity), 빅-오 표기법(Big-O Notation)을 공부하여 내가 한 코딩에 부여된 시간 복잡도를 고려해봐야 할 것 같다.

또한 Map은 key를 이용하여 내부탐색을 진행하는 작업이 필요할 때 유용하다는것을 잊지말자.