프로그래머스 | LV.1 달리기 경주 - HashMap 단순 구현 문풀 (Java)

⬛ 프로그래머스 | LV.1 달리기 경주 - HashMap 단순 구현 문풀

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

프로그래머스

문제 설명

---

💚문제 접근 방식

• 기존 players의 등수가 주어지면 calling가 불리는 이름을 앞등수와 swap시켜 추월시키는 문제이다.

그런데, 처음에 풀면서 시간 초과가 났다. players는 최대 5*10^4 이고, callings가 최대 10^6 이기 때문에 이중for문 돌면 10^10이 되어 시간 초과가 난다. 즉, 이문제의 관건은 이중for문을 돌지 않고 최대한 효율적으로 callings에 해당하는 사람의 idx를 지칭하고, 그 앞사람과의 swap 처리를 하는 게 관건이다.

 

→ HashMap을 활용하여 key에 String을 담고, value에 등수를 주어 매번 효율적으로 추월 대상자의 idx를 얻어오는 식으로 풀면 map.get(key) 가 바로 인덱스를 뱉는데, 이 작업은 평균 O(1) 이다. 

1) HashMap초기화 (players의 초기 등수)

2) calling 순회하면서 현재 추월자의 idx를 map으로 얻어옴

3) players에 현재 추월자와 앞사람 순위 교체시켜줌

4) map도 교체 시켜줌 (그래야 다음 접근 시에도 정확한 idx 주므로)

💚 제출 코드

import java.util.*;

class Solution {
    private static Map<String , Integer> map;
    //솔루션 함수 
    public String[] solution(String[] players, String[] callings) {
        map = new HashMap<>();
        
        for(int i=0; i<players.length; i++){
            map.put(players[i], i);//인덱스랑 함께 담음 
        }
        
        for(String x : callings){
            int own = map.get(x);//현재 등수
            String beforeName = players[own-1];
            
            players[own-1] = x;
            players[own] = beforeName;
            
            //map 세팅
            map.put(x, own-1);
            map.put(beforeName, own);
        }

        return players;
    }
}

💚 시간복잡도

처음에 players 1번 순회하며 map 세팅해줄 때 최악 O(5만) 돌고, calling를 1번 순회하면서 최악으로 O(10^6) 돌며 처리했다. 따라서 둘을 이중for문 돌 경우 10^4 * 10^6 = 10^10이 되므로 최대한 1번의 순회해서 집약적으로 필요한 처리만 하는 게 중요하다.

결과적으로 제출한 코드는 O(5만+100만) = O(105만)이라서 이중 for문 안돌고도 10^6 정도면 시간 내 동작한다고 봤다.

💚 회고

lv1이긴 하지만, 제한사항의 데이터 크기를 고려해서 단순하게 접근하지 않고 더 효율적인 코드 구현을 고려해야 했던 문제이다.

특히나 쉬운 문제의 경우에 예제 통과는 쉬운데 결국 최종 제출 시 시간복잡도가 터져 실패가 뜨는 케이스가 많다. 시간복잡도 잘 따지자.