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

---

🔸문제점

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

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;
    }
}

결과는~~

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

---

🔸시도해본 것들

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

  
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;
    }
}

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

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

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

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

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

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를 이용하여 내부탐색을 진행하는 작업이 필요할 때 유용하다는것을 잊지말자.