HashMap

HashMap 리마인드

callings 값이 나올 때마다 해당되는 players 값의 위치를 변경하면 되는 문제이다.

1. List 사용

	List<String> list = new ArrayList<>(Arrays.asList(players));
	
	for(int i = 0; i < callings.length; i++) {
		for(int j = 0; j < players.length; j++) {
			if(list.get(j).equals(callings[i])) {
				Collections.swap(list, j, j-1);
			}
		}
	}

테스트 케이스에서 시간초과가 일어났다.

2. HashMap 사용

		Map<Integer, String> map = new  HashMap<>();
	
        for(int i= 0; i < players.length; i++) {
            map.put(i, players[i]);
        }
        
        String temp = "";
        
        for(int i = 0; i < callings.length; i++) {
            for(int j = 0; j < map.size(); j++) {
                if(map.get(j).equals(callings[i])) {
                    temp = map.get(j);
                    map.put(j, map.get(j-1));
                    map.put(j-1, temp);
                }
            }
	    }

테스트 케이스에서 시간초과가 일어났다.

3. for문으로 돌리지 말고 key value로 값을 찾아 list를 swap 해주었다.

		Map<String, Integer> map = new  HashMap<>();
        List<String> list = new ArrayList<>(Arrays.asList(players));

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

        for(String calling : callings) {
            // map 몇번째에 있는지
            int rank = map.get(calling);
            String temp = list.get(rank-1);
            map.put(calling, rank-1);
            map.put(temp, rank);

            Collections.swap(list, rank, rank-1);
        }
        
        String[] answer = new String[list.size()];
        
        list.toArray(answer);
        return answer;
        }

통과되었다.

그렇다면 이유가 뭘까?

우선 Hash의 뜻과 특징을 정리해 보자

Hash란?

뒤섞는다는 뜻이 있다.
어떤 데이터를 숫자나 고유 코드로 바꾸는 작업을 말한다.

Hash는 전화번호부와 같다.
예를 들면 "로라" -> 해시 함수로 계산 -> 위치 1에 저장
찾을 때도 "로라" -> 해시 함수로 계산 -> 위치 1에서 꺼냄
즉 로라를 해시 함수를 써서 1 위치에 저장하고 다시 꺼낼 때도 똑같은 해시 함수를 써서 정보를 꺼낸다.

Hash의 특징

1. 찾고 저장하는 속도가 빠르다.
2. 긴 데이터도 짧은 고유 숫자 코드로 바뀐다.(String 문제가 자주 출제)
3. 데이터 무결성(해시 값을 보고 원래 값을 알아내는 건 불가능하다, 비밀번호 암호화)

원인

만약 수많은 데이터값이 있다면 일일히 for 문을 돌려 찾는 것은 시간이 배로 걸릴 수 있다. 그래서 hash를 활용해 특정 데이터값을 넣었을 때 내가 원하는 값을 바로바로 찾을 수 있다.