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

 

내 풀이 - 1 (시간초과)

import java.util.*;

class Solution {
    
    public Map<String, Integer> swap(Map<String, Integer> map, String call) {
        int call_idx = map.get(call);
        // System.out.println(call_idx);
        
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            // System.out.println(key +":"+ value);
            if(value == call_idx-1) {
                map.put(key, value+1);
                // System.out.println("change key: " + key);
            }
            if(key.equals(call)) {
                map.put(key, value-1);
                // System.out.println("change call: " + key);
            }
        }
        return map;
    }
    
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0; i<players.length; i++) {
            map.put(players[i], i);
        }
        
        for(int i=0; i<callings.length; i++) {
            String call = callings[i];
            map = swap(map, call);
        }
        
        map.forEach(
            (k,v) -> 
                // System.out.println(k +":"+ v)
                answer[v] = k
        );
        
        // System.out.println();
        // System.out.println(Arrays.asList(answer));
        return answer;
    }
}

내 풀이 - 2 (시간초과)

import java.util.*;

public class P_48 {
	
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        Map<String, Integer> map = new HashMap<>();
        
        // map으로 플레이어별 인덱스 매핑
        for(int i=0; i<players.length; i++) {
            map.put(players[i], i);
        }
        
        for(int i=0; i<callings.length; i++) {
            String call = callings[i];
            int call_idx = map.get(call);
            int front_idx = call_idx-1;
            // 스왑
            // 앞에 있던 유저 인덱스 변경
            for(String key:map.keySet()) {
            	if(map.get(key).equals(front_idx)) { // 값 으로 앞 유저 찾기
            		map.put(key, call_idx);
                    break;
            	}
            }
            // call한 유저 인덱스 변경
            map.put(call, front_idx);
        }
        
        map.forEach(
            (k,v) -> 
                // System.out.println(k +":"+ v)
                answer[v] = k
        );
        
        // System.out.println();
        // System.out.println(Arrays.asList(answer));
        return answer;
    }
}

풀이 1,2번으로 주어진 테스트 케이스는 통과 했으나 전체 통과는 못했다.

아마 배열에 많은 값들이 있을 경우 너무 오래걸려서 시간 초과가 나는 듯 했다.

 

배열에 데이터가 많으면 많을수록 데이터를 찾는데 오래 걸리기 때문이다.

하지만 HashMap에서는 특정 데이터를 접근할때 키 값으로 바로 찾아 갈 수 있기 때문에 데이터가 아무리 많아도 

속도가 느려지지 않는다.

 

하지만 풀이2에서 해쉬맵을 통해서 문제를 풀었는데도 시간 초과가 났다.

스왑하는 과정에서 해쉬맵을 이용했지만 푸는 방법을 배열처럼 데이터 하나하나 다 돌게끔 코드를 작성 했기 때문이다.

해쉬맵을 이용만 했을뿐 방법은 배열을 가지고 푼거랑 차이가 없었던 것 이다.

 

내 풀이 - 3 (통과)

import java.util.*;

class Solution {
    
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> map = new HashMap<>();
        
        // 플레이어 이름과 순번 map에 담기
        for(int i=0; i<players.length; i++) {
            map.put(players[i], i);
        }
        // 스왑
        for(int i=0; i<callings.length; i++) {
            String call = callings[i];
            int call_idx = map.get(call);
            String front = players[call_idx - 1];
            int front_idx = map.get(front);
            players[call_idx] = front;
            players[front_idx] = call;
            // map도 바꿔주기
            map.put(front, call_idx);
            map.put(call, front_idx);
        }

        return players;
    }
}

이번에는 데이터를 찾아가는 방식을 해쉬맵의 특징을 이용해서 잘 문제를 풀었다.

배열 데이터 도는거는 주어진 플레이어와 콜링의 배열뿐이고 스왑하는 과정에서 해쉬맵의 특징인 값으로 바로 찾아가는 방식으로 풀었다.

이렇게 했더니 시간 초과문제를 해결 하였다.