[프로그래머스] '달리기 경주' - Java

<문제 제시>

<문제설명>
선분 세 개로 삼각형을 만들기 위해서는 다음과 같은 조건을 만족해야 합니다.

>> 가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 합니다.
삼각형의 두 변의 길이가 담긴 배열 sides이 매개변수로 주어집니다. 
나머지 한 변이 될 수 있는 정수의 개수를 return하도록 solution 함수를 완성해주세요.

<예시 입출력>

---

<문제 해결 과정>

equals() 와 같은 메서드로 이중for문을 돌며 간단히 풀어낼 수 있을거라 생각했지만,

시간제한을 신경써야하는 문제였다.

Try 1) 

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


//	        현재 등수 = String[] players
//	        해설진이 부른 이름 = String[] callings
//	        
//	        경기 끝났을때의 선수들의 이름을 1등부터 순서대로 출력      

String temp = "";
for(int i = 0; i < callings.length; i++){
    for(int j = 0; j < players.length; j++){
        if(callings[i].equals(players[j])){
            temp = players[j];
            players[j] = players[j-1];
            players[j-1] = temp;
            //System.out.println(Arrays.toString(players));
        }
    }
}

// answer에 옮기기
for(int i = 0; i < players.length; i++){
    answer[i] = players[i];
}

return answer;

temp를 이용해 값들을 바꿔가며 누적하고자 하였다.

해설진이 부르는 이름을 i로 두고, 업데이트할 players배열을 j로 두어

예를들어 "kai"가 불려질때, players배열을 순회하며 일치하는 '선수 이름'이 있다면, temp로 순서를 바꾸어 업데이트해주었다.

하지만 시간초과가 발생하였다.

Try 2)

String[] answer = new String[players.length];
        
HashMap<String, Integer> goal = new HashMap<>();

// 배열의 값을 Map에 옮겨줌
for(int i = 0; i < players.length; i++) {
    goal.put(players[i], (i+1));
}

System.out.println("goal map의 데이터 = " + goal + "\n");

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

    // 추월 당할 선수 이름 = temp 
    temp = players[ goal.get(callings[i]) - 2 ];

    // 추월 당한 선수의 자리 = players[ goal.get(callings[i]) - 2]
    // 해설진이 호명한 선수 = players[ goal.get(callings[i]) - 1]
    players[ goal.get(callings[i]) - 2] 
            = players[ goal.get(callings[i]) - 1];
    System.out.print(players[ goal.get(callings[i]) - 1] + "선수가 ");

    // 호명된 선수의 자리에 temp(추월당한 선수의 이름)을 업데이트
    players[ goal.get(callings[i]) - 1] = temp;

    System.out.println(temp + "선수를 추월 하였습니다.");

    goal.put(callings[i], goal.get(callings[i]) - 1);
    goal.put(temp, goal.get(temp) + 1);

    System.out.println((i+1) + "번째 호명 = " + goal + "\n");

}

// 
for(int i = 0; i < answer.length; i++) {
    answer[i] = getKey(goal, i+1);
}

return answer;

// hashmap value로 key찾기 >> 랭킹순위로 선수이름 찾기
public static <K, V> K getKey(Map<K, V> map, V value) {

for(K key : map.keySet()) {
    if(value.equals(map.get(key))) {
        return key;
    }
}

return null;

for문으로만 풀면 시간초과가 발생하여 map을 활용하여 풀고자 하였다.
>> 하지만 이 또한 몇몇 테스트케이스를 통과하지 못하고 시간초과가 발생하였다.

answer라는 배열을 리턴하여 값을 얻고자하였으나, players가 이미 수시로 업데이트 되어서

결과값과 동일하므로 answer라는 배열을 따로 만들어서 반환할 필요없이 그대로 players를 리턴해주면 되는 문제였다.
>> 불필요한 getKey의 함수를 지우고, return값을 players로 바꿔야했다. 

cf) HashMap에 값을 넣을때는 HashMap은 순서를 보장하지 않는다.
>> 어떠한 경우에도 키 또는 값을 기준으로 정렬되지 않는다.
>> 키의 해시 값을 기반으로 요소를 정렬하기 때문이다.

정렬되지 않은 HashMap 데이터들

Q. 코드에서 temp에 players[ goal.get(callings[i]) - 2 ]; 를 넣는 이유?
>> 
1) goal.get(callings[i]) 를 하게 되면 "해설진이 호명한 선수"를 가져오고
2) 그 선수의 키 값을 get하므로, 예를 들어 "kai"가 불리게되면, hashmap(goal)로 부터 kai가 속한 키 값을 가져오게 된다.
3) 처음 HashMap을 초기화할때 Integer값을 i+1로 초기화하였기때문에 1~5순위를 가지며, kai일 경우 4가 불러와진다.
4) players[ 4 - 2 ] 인데, -2를 차감값으로 둔 이유는 HashMap을 i+1로 초기화하였기때문에 기존 인덱스 값을 참조하려면 -1이어야하고,
추월하는 로직을 구현하기위해서는 해설진이 부른 선수의 "앞 선수"를 먼저 temp에 저장하고, 업데이트 시켜야하므로
해설진이 부른 선수의 인덱스보다 앞에 있는 (-1)인 선수의 인덱스를 참조해야하므로, 
-1 + -1 = -2의 차감값을 가지게 된다.

5) 결국 players[2] 가  players[3]으로 업데이트되고, players[3]은 players[2]로 업데이트된다.

Solution 1)

향상된 for문 사용과 인덱스를 참조하는 부분을 통일하여 코드를 간소화하고자 하였다.

for(String calling : callings) {
    int idx = goal.get(calling);

    if(idx > 0) {
        // 추월 당할 선수 이름 = temp
        String temp = players[idx - 1];

        players[idx - 1] = players[idx];

        players[idx] = temp;

        goal.put(players[idx - 1], idx - 1);
        goal.put(players[idx], idx);
    }

}

---

<전체코드>

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

public class racing {

	public static String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> goal = new HashMap<>();
        
        // 배열의 값을 Map에 옮겨줌
        for(int i = 0; i < players.length; i++) {
        	goal.put(players[i], i);
        }
        
        System.out.println(goal + "\n\n");
        
        for(String calling : callings) {
        	int idx = goal.get(calling);
        	
        	if(idx > 0) {
        		// 추월 당할 선수 이름 = temp
            	String temp = players[idx - 1];
            	
            	players[idx - 1] = players[idx];
            	
            	players[idx] = temp;
            	
            	goal.put(players[idx - 1], idx - 1);
            	goal.put(players[idx], idx);
        	}
        	        	
        }
        
        return players;
	}
	
	public static void main(String[] args) {
		String[] players = {"mumu", "soe", "poe", "kai", "mine"};
		String[] callings = {"kai", "kai", "mine", "mine"};
		
		System.out.println(Arrays.toString(solution(players, callings)));
	}

}

return값이 배열형식이므로 HashMap을 배열로 넣기위해,

배열의 answer[i]처럼 인덱스 값을 통해 value를 찾는 getKey 함수를 만들어 

HashMap을 다루는 함수를 작성할 수 있었다. 

>> 하지만 시간초과가 발생하였고, 배열로 넣는 부분 또한 
업데이트된 players를 단순히 리턴시키면 된다는 것을 알 수 있었다. 

향상된 for문과 인덱스 참조부분을 통일시켜 코드를간소화하였다.

---

속도개선을 위하여 HashMap의 사용법을 익힐 수 있었다.

players[i]를 참조할때 i값을 [goal.get(callings[i]) - 2]처럼 참조한다는 것 또한 공부해야할 문제였다.

---

문제링크)
https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스