[프로그래머스] 달리기 경주

내가 좋아하는거 두개 다 있넹 ㅎㅎ 달리기와 경주(장군 암소 숯불 영원해..)

사기 map을 써서 풀어야지~ 하고 풀었다가 냅다 시간초과가 떴다.

이유를 생각해보면 players의 길이와 callings의 길이가 굉장히 길다. 이 문제는 시간 복잡도를 잘 설계해라 문제같음.

 

첫번째 풀이 : map에 key값으로 선수 이름, value값으로 현재 등수를 넣음

calling에서 현재 선수가 불리면? map에서 불린선수의 value값과, 불린선수의 앞 선수의 value값을 서로 바꿔주면 된다 

*여기서 시간초과*

내가 아직 map을 다루는게 완벽하지 않은건지 value값으로 key값을 찾는게 어렵다. 이걸 구글링을 해봐도 map에서 직접적으로 메서드를 통해서 안해준다고 함. 따라서 반복문을 새로 돌면서 해당 key값이 value값과 동일 할 때의 key값을 반환하는 식(indexOf와 비슷한 느낌)으로 풀었다.

이렇게 되면 또 반복문 안에 indexOf가 들어가는 느낌... -> 바로 시간초과 떠버렸다.

 

두번째 풀이 : map을 왜씀 배열로 그냥 바로 때려

생각해보니까 이거 map 안써도 될 거 같음. 그래서 String[]로 바로 풀어보려고 했다. 그런데 이는 위와 마찬가지 로직임.

어짜피 callings에서 나오는 String의 인덱스를 찾아줘야함. 찾아줄 때 indexOf처럼 다시 반복문으로 서칭을 해줘야 하기 때문에 시간적으로 같음.

 

[정답]세번째 풀이 : 이정도 했으면 이제 내 소관을 떠났다. 어떻게 해야 시간을 줄일 수 있는지 답을 찾아봄

map을 2개 써준다. 한개는 key값에 선수 이름, value값에 현재 등수. 다른 짝이 되는 map은 key값과 value값을 반대로 매핑해줌. key값에 현재 등수, value값에 선수 이름

이런식으로 두개의 map을 사용하게 되면 index를 찾기 위한 반복문을 사용하지 않아도 됨.

callings에서 나온 String값을 map으로 찾아서 value를 찾음. 그렇게 나온 value는 짝이 되는 mapRank의 key값으로 들어감.  이건 시간복잡도가 빠름.

 

핵심 로직 : callings에서 나온 String값을 map.get(call)로 value(rank)를 찾음. 그리고 mapRank.get(rank-1)은 현재 불린 선수의 앞 선수의 이름을 가짐. 이를 서로 스왑 해주면 됨.

 

시간 복잡도가 점점 내 발목을 잡는 걸 보니 이제 정말 시간 복잡도를 신경 써야 할 타이밍이 왔나보다.

 

 

풀이

// 첫번째 풀이 : 참가자 등수대로 map에 저장. key : 플레이어 이름. value : 현재 등수
// 참가자 이름이 불리면 value -1, 불린 참가자의 앞사람 value를 불린사람 값으로 교환
// 실패 -> 시간초과 뜸

// 두번째 풀이 String[]배열로 풀었는데 마찬가지로 시간초과..

// 공부를 해보니까 해쉬를 이용해서 풀어라 -> 해쉬가 뭐임?? -> key, value를 사용. ?? 이거 맵인데?
// 다시 맵으로 풀어본다 // key로 value를 찾는게 시간이 오래걸림. 쌍으로 존재하는 이 값들을 어떻게 찾지

//메모리를 포기하고 시간을 줄이는 방법. 나는 map을 두개 써서 value로 key를 찾는 시간을 줄임

import java.util.Map.*;
import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> map = new HashMap<>();
        Map<Integer, String> mapRank = new HashMap<>();
        String player;
        int rank;
        String[] answer = new String[players.length];
        for(int i=0;i<players.length;i++){
            map.put(players[i], i);
            mapRank.put(i, players[i]);
        }
        for(String call : callings){
            rank = map.get(call);
            player = mapRank.get(rank-1);
            
            map.put(player, rank);
            map.put(call, rank-1);
            
            mapRank.put(rank, player);
            mapRank.put(rank-1, call);
            
        }
        
        //확인용 출력
        // for (Entry<String, Integer> entrySet : map.entrySet()) {
        //     System.out.println(entrySet.getKey() + " : " + entrySet.getValue());               }
        // System.out.println();
        // for (Entry<Integer, String> entrySet : mapRank.entrySet()) {
        //     System.out.println(entrySet.getKey() + " : " + entrySet.getValue());               }
        
        
        for(int i=0;i<players.length;i++){
            answer[map.get(players[i])] = players[i];
        }
        return answer;
    }
}