달리기 경주

문제

프로그래머스

 

---

코드

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

public class Solution {
	String[] answer;
	Map<String, Integer> indexMap;

	public String[] solution(String[] players, String[] callings) {
		answer = players;
		indexMap = new HashMap<>();

		for (int i = 0; i < players.length; i++) {
			indexMap.put(players[i], i);
		}
		for (String call : callings) {
			swap(findIndex(call));
		}
		return answer;
	}

	// 인덱스 찾기
	private int findIndex(String call) {
		return indexMap.get(call);
	}

	void swap(int i) {
		// 인덱스 갱신
		indexMap.put(answer[i - 1], i);
		indexMap.put(answer[i], i - 1);
		// 스왑
		String tmp = answer[i - 1];
		answer[i - 1] = answer[i];
		answer[i] = tmp;
	}
}

---

HashMap이 핵심이다. 

해시를 이용해 자료 접근에 필요한 시간 복잡도를 상수 1 로 만든다.

 

추가로 swap()에서 반드시 indexMap을 갱신해줘야 한다.