[Java 자바 프로그래머스] level.1 달리기경주 (+시간초과오류 해결)

🔒문제

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

---

🔌문제 접근

players 배열에서 현재 달리고 있는 순위랑 선수이름을 연결해놓으면
callings 배열에 있는 선수 이름이 하나씩 나올 때마다 순위를 바꾸기 쉽다

 

여기서부터 시작해서 맨 처음 떠올린 방법은

List 를 이용하는 것이었다. List는 특정 인덱스에 값을 추가하고 삭제하는 게 가능하기 때문

이 두 메서드 (add / remove)를 사용해서 금방 코드를 짤 수 있었다.

 

import java.util.*;

public class Solution {
    public String[] solution(String[] players, String[] callings) {
		 String[] answer = {};

		 List<String> players_list = new ArrayList<>(Arrays.asList(players));

		 changeRank(callings, players_list);

		 return players_list.toArray(answer);

	 }

	 private static void changeRank(String[] callings, List<String> players_list) {
		 for(int i=0;i<callings.length;i++) {
			 int rank = players_list.indexOf(callings[i]);

			 players_list.remove(rank);
			 players_list.add(rank-1,callings[i]);
		 }
	 }
}

 

 결과 👉 시간 초과 오류

---

❔원인

List 클래스의 indexOf, remove, add 메서드의 시간 복잡도는 O(N)이다.
따라서 위의 코드처럼 players 길이만큼의 List를 callings의 길이만큼 반복한다면
시간 복잡도는 50,000 x 1,000,000 이 된다.

 

🧩해결방법

프로그래머스 질문 게시판을 찾아보니까

Map 클래스는 바로 key의 값으로 value를 검색하기 때문에 시간복잡도는 N(1) 이라고 한다.
Map 클래스를 사용하면 시간복잡도를 많이 줄일 수 있다.

시간복잡도 비교

---

🔓풀이 코드

Map1 = [ 선수이름, 순위 ] 
Map2 = [ 순위, 선수이름 ] 
두 가지의 해쉬맵을 만들어서 순위가 바뀔 때마다 map1과 map2의 데이터를 수정한다.

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public String[] solution(String[] players, String[] callings) {
		 String[] answer = new String[players.length];
	        
		 Map<String, Integer> byRunner = new HashMap<>();
		 Map<Integer, String> byRank= new HashMap<>();
		 
		 for(int i=0;i<players.length;i++) {
			 byRunner.put(players[i], i);
			 byRank.put(i, players[i]);
		 }
		 
		 for(int i=0;i<callings.length;i++) {
			 int currentRank = byRunner.get(callings[i]);
			 String runner = byRank.get(currentRank);
			 
			 String frontRunner = byRank.get(currentRank-1);
			 
			 //RankMap에서 바꾸기
			 byRank.replace(currentRank-1, runner);
			 byRank.replace(currentRank, frontRunner);
			 
			 //RunnerMap에서 바꾸기
			 byRunner.replace(frontRunner, currentRank);
			 byRunner.replace(runner, currentRank-1);
		 }
		 
		 for(int i=0;i<players.length;i++) {
			 answer[i] = byRank.get(i);
		 }
		 
		 return answer;
	 }
}