[Programmers / Level1] 178871. 달리기 경주(Java)

💡 Info

---

• 난이도: Lv1
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/178871
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/1/178871. 달리기 경주

입출력 조건

---

입출력 예시

---

문제 이해

---

• 선수의 이름을 부르는 순대로 랭킹이 결정되고, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 반환하면 되는 문제.

알고리즘

---

풀이 시간 : 20분

• 추월한 선수에 대한 인덱스 부여하기
• 추월한 선수와 그 앞에 있는 선수를 교체하기
  • callings 길이만큼 반복

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = players;
        
        List<String> answerArr = Arrays.asList(answer);
        
        for(int i=0; i<callings.length; i++){
            int rank = answerArr.indexOf(callings[i]);
            String changeName = answer[rank-1];
            
            answer[rank-1] = answer[rank];
            answer[rank] = changeName;
        }
        return answer;
    }
}

오답체크

---

• 시간 초과 문제 발생
  • Map을 활용하는 방향으로 전환

//before
List<String> answerArr = Arrays.asList(answer);

//after
Map<String, Integer> answerMap = new HashMap<>();
        
for(int i=0; i<players.length; i++){
	answerMap.put(players[i], i);
    
    answerMap.put(answer[rank-1], rank-1);
    answerMap.put(answer[rank], rank);
}

최종 풀이 1

---

풀이 시간 : 30분(첫 풀이 시간 포함)

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = players;
        
        Map<String, Integer> answerMap = new HashMap<>();
        
        for(int i=0; i<players.length; i++){
            answerMap.put(players[i], i);
        }
        
        for(int i=0; i<callings.length; i++){
            
            int rank = answerMap.get(callings[i]);
            String changeName = answer[rank-1];
            
            answer[rank-1] = answer[rank];
            answerMap.put(answer[rank-1], rank-1);
            
            answer[rank] = changeName;
            answerMap.put(answer[rank], rank);
        }
        return answer;
    }
}

최종 풀이 2

풀이 시간 : 35분(첫 풀이 시간 포함)

• 추월한 선수에 대한 인덱스 부여하기
• 추월한 선수와 그 앞에 있는 선수를 교체하기
  • callings 길이만큼 반복

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = players;
        
        Map<String, Integer> answerMap = new HashMap<>();
        
        for(int i=0; i<players.length; i++){
            answerMap.put(players[i], i);
        }
        
        //for(int i=0; i<callings.length; i++){
        for(String player : callings){
            
            //int rank = answerMap.get(callings[i]);
            int rank = answerMap.get(player);
            String changeName = answer[rank-1];
            
            answer[rank-1] = answer[rank];
            answerMap.put(answer[rank-1], rank-1);
            
            answer[rank] = changeName;
            answerMap.put(answer[rank], rank);
        }
        return answer;
    }
}

결과

• 풀이 1
  
  

• 풀이 2