해시 (전화번호 목록)

먼저 위 문제를 분석을 해보았을 때

1. phone_book의 각 String 값을 HashMap에 동일한 부분이 있으면 넣지 X, 없으면 Hash에 넣는다.

 

2. HashMap에 넣게된다면 동일한 key가 없기 때문에, 동일하게 접두사 부분이 있으면 길이가 줄어든다.
  (*따라서 phone_book의 길이와 Hash에 넣은 길이가 다르면 접두사가 있다는 말)

 

1번을 어떻게 구현을 해야할지,, 너무 생각보다 너무 잘 안떠올라서 이래저래 생각도 해보고, 머리 아파서

침대에 누웠는데 어떻게 할지 생각이 났다. (*그런데 피곤해서 자다가 일어나서 만들었다는 것ㅋㅋㅋ)

내가 생각한 방법은 접두사는 앞에서 붙이는 부분이기 때문에 String의 값을 charAt()으로 한개씩 불러오는 것이었다.

 

각 String을 불러올때 String을 1자리씩 붙여서 만든후, 동일한 접두사가 있으면 빠져나오고, 없으면 새로운 값을

Hash에 input 하였다.

(*여기서 또 예외가 있었는데, 처음부터 짧은 글자가 아닌, 긴 글자가 먼저 나왔을 때 ex) {1235, 123, 12}

 각각 따로 hash에 등록이 되기 때문에 먼저 Arrays.sort()를 이용해서 정렬을 하고 시작했다.)

 

java에서 많이 사용하는 HashMap을 처음 사용했던 유형의 문제였던 것 같다.

처음에는 해쉬 문제 중 일부 문제를 배열로 풀었으나, 답은 맞아도 효율성부분에서 통과하지를 못했다.

배열과 HashMap을 사용했을 때 장점이 무엇이 있을까?

 

1. 먼저 배열을 탐색할 때 0 -> n-1의 길이까지 탐색해야해서 O(n)이 걸리지만

   HashMap은 (key, value)로 구성되어 있어 탐색시간이 O(1)이다.

   (*값을 찾는데에 있어서 속도를 비교해보았을 때 훨씬 빠르다.)

 

2. HashMap은 key의 중복값을 생성하지 않는다.

 

(또 한 블로그에서 HashSet과 HashMap의 차이에 대해서 너무 잘 설명해주는 내용이 있어서 가져왔다. ↓↓)

- HashSet과 HashMap의 차이 (Java에서)

HashMap
1. HashMap은 Map 인터페이스를 구현했다.(implement)
2. HashMap은 데이터를 key-value 형식으로 저장한다.
3. put() 메소드는 데이터를 넣을 때 사용된다.
4. HashMap에서 hashcode 값은 key value를 이용하여 생성한다.
5. HashMap은 unique key를 이용하여 데이터에 바로 접근하기에 HashSet에 비해서 빠르다.

 

HashSet
1. HashSet은 Set 인터페이스를 구현했다.(implement)
2. HashSet은 객체만 저장할 수 있다.
3. add() 메소드를 통해 데이터를 저장한다.
4. 들어가는 객체를 이용하여 hashcode를 생성하고, equal() 메소드를 이용해 hashcode를 비교, 중복된 객체가 있는지 체크한다. (equal() 메소드는 중복된 객체가 있으면 true를, 없으면 false를 리턴한다.
5. HashMap에 비해 느리다.

출처: https://postitforhooney.tistory.com/entry/JavaHashSet과-HashMap [PostIT]

 

●코드

*출처 : programmers.co.kr/learn/courses/30/lessons/42577