달리기 경주 문제풀이

현재 순위대로 선수 배열이 주어지고 

callings 배열이 주어진다. 

해설진은 앞 선수를 한명 추월할 때마다 한번씩 calling하고 calling 순서대로 담은 배열이 callings 이다.

경기가 끝났을때 선수를 순위대로 담은 배열을 반환 

 

처음엔 순서가 있어서 ArrayList의 indexOf로 쉽게 찾을 수 있을 줄 알았는데 

indexOf도 결국 선형검색을 수행하기 때문에 이중포문과 별 차이가 없어서 시간초과된다. 

 

이름이 불리기 때문에 Map으로 하려고 했는데 

처음엔 map으로 이름 찾는건 좋은데 순서를 바꾸고 순서가 바뀐 map을 다시 배열로 변경하는 작업도 까다로워

결국 시간초과되었다. 

 

해결방법은 생각보다 간단했다.

public String[] solution(String[] players, String[] callings) {

int n = players.length;

HashMap<String, Integer> rank = new HashMap<>();

 

for (int i = 0; i < n; i++) {

rank.put(players[i], i);

}

 

for (String calling : callings) {

int i = rank.get(calling);

String temp = players[i - 1];

players[i - 1] = players[i];

players[i] = temp;

 

rank.put(players[i - 1], i - 1);

rank.put(players[i], i);

}

 

return players;

}

랭크맵으로 다시 선수 순위 배열을 만드는게 아니라 랭크맵은 순위를 참조하기만 하고 players를 조작해 반환한다. 

 

 

 

 맵을 선수 이름으로 순위를 찾는 맵과 순위로 선수 이름을 찾는 맵을 만드는 방법도 있다. 

같은 내용을 키와 값만 바꿔서 두개의 맵을 만들어 사용하는건 다른데서도 쓸 수 있지 않을까싶어 만들어보았다. 

public String[] solution2(String[] players, String[] callings) {

String[] answer = new String[players.length];

Map<String,Integer> a = new HashMap<String, Integer>();

Map<Integer,String> b = new HashMap<Integer,String>();

for (int i = 0; i < players.length; i++) {

a.put(players[i],i);

b.put(i, players[i]);

}

for (int i = 0; i < callings.length; i++) {

int callingsRank = a.get(callings[i]);

a.replace(callings[i],callingsRank-1);

String prev = b.get(callingsRank-1);

b.replace(callingsRank-1, callings[i]);

a.replace(prev, callingsRank);

b.replace(callingsRank, prev);

}

for (int i = 0; i < a.size(); i++) {

answer[i]=b.get(i);

}

return answer;

}