프로그래머스 해시 문제 전화번호 목록 (java)

프로그래머스 해시 문제 전화번호 목록 (java)

해시문제

2. 전화번호 목록

해시개념 - 해시 문제풀이 1번 글 확인

https://healthyhabit.tistory.com/20

-- 해시 알고리즘을 몰랐을 때의 풀이 --

import java.util.Arrays; class Solution { public boolean solution(String[] phone_book) { boolean answer = true; Arrays.sort(phone_book); for(int i = 0 ; i < phone_book.length - 1 ; i ++){ String iString = phone_book[i]; String jString = phone_book[i+1]; if(iString.length() <= jString.length()){ if(iString.equals(jString.substring(0,iString.length()))){ answer = false; break; } } } return answer; } }

문제를 보면 해당 배열에서 접두어가 존재하는지, 접두어가 존재 할 경우 false값, 존재하지 않을 경우 true값 return

- 접두어 : 어떤 단어의 머리에 덧붙이는 말 (사전적 의미)

- 효율성 테스트 -

테스트 1 〉 통과 (19.64ms, 55.7MB) 테스트 2 〉 통과 (32.27ms, 74.3MB) 테스트 3 〉 통과 (355.35ms, 98.1MB) 테스트 4 〉 통과 (324.39ms, 96.7MB)

- HashMap 사용 -

import java.util.HashMap; class Solution { public boolean solution(String[] phone_book) { HashMap hash = new HashMap(); for(String pb : phone_book){ hash.put(pb,pb.length()); } for(String key : hash.keySet()){ for(int i = 1; i < key.length() ; i++){ if(hash.containsKey(key.substring(0,i))){ return false; } } } return true; } }

-- 이중 for문을 사용하기 싫었지만 방법이 생각나지 않는다... 혹시 더 효율적인 방법을 아시는 분은 댓글 부탁드립니다.

- 효율성 테스트 -

테스트 1 〉 통과 (3.43ms, 58.2MB) 테스트 2 〉 통과 (3.67ms, 56.8MB) 테스트 3 〉 통과 (323.37ms, 243MB) 테스트 4 〉 통과 (362.05ms, 187MB)

keySet() : Map 의 Key값을 retrun 한다.

containsKey :

-- containsKey(TKey) Map의 "key"의 값중에서 TKey의 값이 존재하면 True 존재하지 않으면 False를 return한다.

from http://healthyhabit.tistory.com/21 by ccl(A) rewrite - 2021-09-25 12:27:10