소요시간 : 30분
느껴진다… 시간초과가
시간초과를 피하기 위해 Hash 자료구조를 이용해서 문제를 풀어보겠습니다.
아이디어는 이렇습니다.
1. Hash에 이름과 인덱스 번호를 담아둡니다.
2. Hash검색을 통해 인덱스를 찾아내 교체 번호를 바로 파악하고 앞 번호와 교체(swap)
3. Hash맵에도 마찬가지로 교체된 번호를 업데이트를 진행합니다.
바로 코드 보겠습니다.
package Question;
import java.util.HashMap;
/**
* 프로그래머스 달리기 경주
* https://school.programmers.co.kr/learn/courses/30/lessons/178871
*
* 아이디어
* 1. Hash에 인덱스 번호 담아두고
* 2. Hash 검색을 통해 인덱스를 바로 찾아내 교체 번호 확인 바로앞번호와 교체
* 3. Hash맵에도 마찬가지로 업데이트 진행
* */
public class RunningRace {
public static void main(String[] args) {
}
public static String[] solution(String[] players, String[] callings) {
HashMap<String, Integer> map = new HashMap<>();
// HashMap 초기화 작업 진행
for (int i = 0; i < players.length; i++) {
map.put(players[i], i);
}
// callings 시작
for (String s : callings){
swap(players, map, map.get(s), map.get(s)-1);
}
String[] answer = players;
return answer;
}
public static void swap(String[] players, HashMap<String,Integer> map , int changeIndex1, int changeIndex2 ){
// 먼저 map 부터 업데이트
map.put(players[changeIndex1] , changeIndex2);
map.put(players[changeIndex2] , changeIndex1);
String temp = players[changeIndex1];
players[changeIndex1] = players[changeIndex2];
players[changeIndex2] = temp;
}
}
아이디어 처럼 swap 이 진행될때 Hash도 같이 업데이트 되는 것을 볼수 있습니다.
