[프로그래머스] Lv1. 달리기 경주 (Java)

프로그래머스

 

===문제 설명===

해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다.

예를 들어 1등부터 3등까지 mumu, soe, poe 선수들이 순서대로 달리고 있을 때, 해설진이 soe 선수를 불렀다면, 2등인 soe 선수가 1등인 mumu 선수를 추월했다는 것입니다.

즉 soe 선수가 1등, mumu 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

---

🌟 T I P 🌟

callings의 길이는 최대 1,000,000이기 때문에 시간복잡도를 최대한 O(n) 또는 O(nlogn) 이하로 구해야 한다는 것을 짐작할 수 있습니다.

 

따라서 HashMap을 활용해 등수와 이름을 저장해, 이름과 등수를 찾는 시간을 O(1)로 하려고 합니다.

 

🔖 풀이과정

1.  <key, value> 값이 <선수이름, 등수>인 HashMap과 <등수, 선수이름>인  HashMap을 둘 다 만들어 줍니다.

여기에 주어진 players의 선수이름과 등수를 저장합니다.

HashMap<Integer,String> rank_name = new HashMap<>();//등수-이름
HashMap<String,Integer> name_rank = new HashMap<>();//이름-등수

for(int i=0;i<players.length;i++){
    rank_name.put(i,players[i]);
    name_rank.put(players[i],i);
}

 

2. callings에서 불린 순서대로 선수 이름을 가져와줍니다.

불린 선수의 등수를 name_rank HashMap에서 get 해줍니다.

for(int i=0;i<callings.length;i++)
    int rank = name_rank.get(callings[i]); //불린 사람이 몇등인지 get

 

3. 불린 사람(추월한 사람)과 추월당한 사람의 등수를 바꿔줍니다.

int rank = name_rank.get(callings[i]); //추월한 사람 = 불린 사람

rank_name.put(rank,rank_name.get(rank-1);//추월당한 사람을 rank 등수로 강등.
name_rank.put(rank_name.get(rank-1),rank);

rank_name.put(rank-1,callings[i]);//추월한 사람 rank-1로 등수 올림 : 추월
name_rank.put(callings[i],rank-1);

 

4. 0등부터 마지막 등수까지 answer배열에 순서대로 선수 이름을 넣어줍니다.

for(int i=0;i<players.length;i++)
    answer[i]=rank_name.get(i);//i등 - 선수이름

---

전체 코드

import java.util.*;
class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        
        HashMap<Integer,String> rank_name = new HashMap<>();//등수-이름
        HashMap<String,Integer> name_rank = new HashMap<>();//이름-등수
        for(int i=0;i<players.length;i++){
            rank_name.put(i,players[i]);
            name_rank.put(players[i],i);
        }
        for(int i=0;i<callings.length;i++){
            int rank = name_rank.get(callings[i]);//불린 사람이 몇 등인지
            
            //등수 바꿔주기.
            rank_name.put(rank,rank_name.get(rank-1));
            name_rank.put(rank_name.get(rank-1),rank);
            name_rank.put(callings[i],rank-1);
            rank_name.put(rank-1,callings[i]);
            
        }
        //0~등부터 answer배열에 넣기
        for(int i=0;i<players.length;i++)
            answer[i]=rank_name.get(i);
        
        return answer;
    }
}