문제링크

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

구현방법

처음 계산은 2중for으로 진행을 했다가 계산되는 시간을 따져보니 O(n^2)으로는 시간초과가 발생한다는 문제를 깨달았습니다.

그래서 위와같은 Key,Value를 같는HashMap 2개를 만들었습니다.

• 이름,순위
• 순위,이름

calling을 돌면서 현재 이름을 불린 name을 찾아서 순위를 반환받고 그전 순위인 이름도 찾아야하기 때문에 before_rank로 그전 순위를 체크해둡니다. tmp에 그전 순위의 이름을 받아두고 둘을 스왑해서 갱신해줍니다.

구현알고리즘

HashMap

CODE

import java.util.Arrays;
import java.util.HashMap;

//테스트용
public class Main {
    public static void main(String[] args) {

        String[] answer = new Solution().solution(new String[]{"mumu","soe","poe","kai","mine"},new String[]{"kai","kai","mine","mine"});
        System.out.println(Arrays.toString(answer));
    }
}
//이름 순위 맵
//순위 이름 맵 

//추월하는 사람 이름 -> key가 이름인 맵으로 등수 체크
//추월 당하는 사람 이름 -> 위에서 구한 등수 -1로 체크
//둘의 위치를 변경하여 갱신
class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];


        HashMap<Integer,String> maps = new HashMap<>();
        HashMap<String,Integer> nameMap = new HashMap<>();
        for(int idx= 0; idx < players.length;idx++){
            maps.put(idx+1,players[idx]);
            nameMap.put(players[idx],idx+1);
        }

        for(int idx = 0; idx < callings.length;idx++){
            String tmp ="";
            String name = callings[idx];
            int name_rank = nameMap.get(name);

            int before_rank = name_rank -1;
            tmp = maps.get(before_rank);

            maps.put(before_rank,name);
            maps.put(name_rank,tmp);

            nameMap.put(name,before_rank);
            nameMap.put(tmp,name_rank);

        }
        for(int check = 0; check < maps.size(); check++){
            answer[check] = maps.get(check+1);
        }


        return answer;
    }
}