프로그래머스 달리기 경주 자바로 HashMap을 사용하여 풀어보기

문제부터 보겠다.

 

 

일단 이 문제를 보고나서 생각한 문제풀이는

중첩 for문을 사용하여 callings의 요소와 일치하는 요소가 players에 있다면

해당 인덱스 자리와 그 앞자리를 바꾸도록 알고리즘을 만들면어떨까하여 바로 코드로 입력해보았다.

 

class Solution {
	    public String[] solution(String[] players, String[] callings) {
	    	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-1];
						players[j-1] = callings[i];
						players[j] = temp;
					}
				}
			}
			return players;
	    }
	}

 

코드 실행에서는 무난하게 통과가 나왔다.

그렇다면 과연 채점은 어떨까?

 

시간 초과로 인하여 오답으로 결과가 나왔다..

 

어찌보면 당연하게도 for문은 하나당 O(n)의 시간복잡도를 갖고

이중 for문의 경우 O(n) * O(n) 만큼의 시간 복잡도를가지게 되므로 O(n^2) 가된다.

 

따라서 이중 for문을 쓰면 매우 느려 시간초과가 될수밖에 없을것이다.

 

그렇다면 어떤 자료구조를 쓰는 것이 좋을까? 

 

검색이 빠르며 값과 인덱스를 같이 저장할수있는 자료구조를 찾아보던중

 

HashMap이라는 자료구조를 알게되었다.

 

HashMap

 

HashMap은 Key , Value 쌍으로 구성되있는 Map 인터페이스의 구현 클래스이다.

HashMap은 삽입,검색에 시간복잡도가 O(n) 이라는 매우 빠른 성능을 가지고있다.

 

그렇다면 HashMap을 사용하여 문제를 풀어보겠다.

 

public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> list = new HashMap<String, Integer>();
			
			int index = players.length;
			String temp;
			//해시맵에 players의 값과 인덱스를 그대로 옮긴다.
			for(int i=0;i<index;i++) {
				list.put(players[i],i);
			}
    }

 

우선 매개변수로 받아오는 값은 일반 배열이니

HashMap을 생성하여 반복문을 통해 players의 값과 인덱스를 삽입시켜준다.

 

for(String cal : callings) {
				int idx = list.get(cal);
				if(idx > 0) {
					temp = players[idx-1];
					players[idx-1] = players[idx];
					players[idx] = temp;
				}
				
				list.put(players[idx-1],idx-1);
				list.put(players[idx],idx);
			}
			return players;

 

그 다음 향상된 for문을 사용하여 callings의 값을 돌려주고

HashMap에서 callings의 요소와 일치한 값에 인덱스값을 찾는다.

 

만약 인덱스가 0 즉 2등 이상이라면 해당 등수의 값과 다음 등수의 값을 서로 바꿔준다.

 

그리고 나서 HashMap에도 똑같이 값을 삽입해주었다.

그리고 결과를 리턴 !!

 

과연 결과는 ??😖

 

통과되었다 ~~~~

 

다음부터는 무조건 반복문을 사용하기보다 어떤 자료구조가 효율적이고 시간복잡도가 어떨지

생각하며 문제를 풀어봐야겠다.