[프로그래머스 Lv.1 Java] 달리기 경주

 

코딩테스트 연습 - 달리기 경주 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

배열에 포함된 원소의 index 찾기 - indexOf()

[JAVA] 배열에서 indexOf() 사용하려면? (tistory.com)

[JAVA] 배열에서 indexOf() 사용하려면?

배열의 길이 - arr.length

배열의 길는 arr.length

List의 크기는 list.size()

---

[문제의 코드]

import java.util.Arrays;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
       
        int n = callings.length;
        int index;
        String temp;
        for(int i=0; i<n; i++){
        
            index = Arrays.asList(players).indexOf(callings[i]);
            temp = players[index];
            players[index] = players[index-1];
            players[index-1] = temp;
        }
        
        for(int i=0; i<players.length; i++){
            answer[i] = players[i];
        }
        
        return answer;
    }
}

 

import java.util.Arrays;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
       
        int index;
        String temp;
        for(String player : callings){
            index = Arrays.asList(players).indexOf(player);
            temp = players[index];
            players[index] = players[index-1];
            players[index-1] = temp;
        }
        
        int i=0;
        for(String player : players){
            answer[i] = player;
            i++;
        }
        
        return answer;
    }
}

 

[해결] - 배열은 처음에 선언할 때 크기를 지정해주어야 하고, 이후에 변경할 수 없다. 

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

첫 줄을 위와 같이 바꿔주니 해결! 

프로그래머스에서 준 첫 줄이라 당연히 문법에 맞게 줬을 줄 ... 

 

---

근데 .. ! 시간 초과 문제 발생

[해결] - Hash Map을 사용해줘야했던 문

 

	get (데이터 접근)
배열	O(n)
HashMap	O(1)

 

HashMap 특정 데이터에 접근할 때 key로 접근하기 때문에 시간복잡도가 O(1)

배열에서는 시간 복잡도는 O(n)

 

시간 초과 문제였기 때문에 자료구조를 Hash Map으로 바꿔줘야했던 것이다. 

자료구조로 꼭 HashMap을 묶어서 저장할 이유가 없는 문제지만, 시간 복잡도 때문에 일단 HashMap으로 push 해야 한다.

 

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

for(int i=0; i<players.length; i++){
	hash.put(players[i], i);
}

---

최종 코드

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> hash = new HashMap<>();

        for(int i=0; i<players.length; i++){
	        hash.put(players[i], i);
        }
       
        int b, tmp;
        String p;
        for(String player : callings){
            //호출된 player의 인덱스(등수)를 저장
            b = hash.get(player);
            //호출된 player가 앞지른 player를 저장, 인덱스 저장
            p = players[b-1];
            tmp = hash.get(p);
            players[tmp] = player;
            players[tmp+1] = p;
            
            //hashMap도 갱신
            hash.put(player, b-1);
            hash.put(p, b);
        }
        
        return players;
    }
}