[programmers] 달리기 경주

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

프로그래머스

 

calling이 최대 1,000,000 이기 때문에 calling 단독 for문이 돌고 그 안에서 문제를 해결해야한다.

 

 

swap 코드 대신 ArrayList의 set을 사용한 코드

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        ArrayList<String> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        
        int index = 0;
        for(String player: players) {
            list.add(player);  
            map.put(player, index++);
        }
        
        for(String calling: callings) {
            int idx = map.get(calling);
            String loser = list.get(idx - 1);
            
            map.put(calling, idx - 1);
            map.put(loser, idx);
            
            list.set(idx - 1, calling);
            list.set(idx, loser);
        }
        answer = list.toArray(answer);
        return answer;
    }
}

 

 

시간 초과 코드

아래와 같이 짜게 되면 1,000,000 * 50,000 으로 시간초과가 발생한다. 따라서 players의 현 위치를 저장하는 코드가 필요하다.

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        for(String calling: callings) {
            for(int i = 0; i < players.length; i++) {
                if (players[i].equals(calling)) {
                    String temp = players[i - 1];
                    players[i - 1] = players[i];
                    players[i] = temp;
                }
            }
        }
        return players;
    }
}