반응형
***정렬을 이용한 c++ 코드가 필요하다면 아래의 블로그를 참고하세요***
2023.10.18 - [CO-TE/challenge] - [프로그래머스] JAVA / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (1)
이번에는 해시 알고리즘을 이용한 java 풀이법을 살펴보겠다.
💡 ''해시 알고리즘''??
해시(hash)는 임의의 데이터를 고정된 길이의 숫자나 문자열로 변환하는 과정이다.
HashMap
- 해시를 사용하는 자료 구조의 일종이다.
- HashMap은 키-값 쌍을 저장하고, 이러한 키-값 쌍에 대한 빠른 검색 및 검색을 지원합니다
- 문자열을 가지고, 해당 문자열이 HashMap에 있는지 바로바로 찾아주기 때문에 O(1)의 복잡도를 갖는다.
HashMap을 활용해서 HashMap에 전화번호 목록들을 키-값 쌍으로 저장하는 과정이 필요하다.
HashMap에 있는 값들은 이제 HashMap에서 지원하는 찾기 함수를 통해서 바로바로 찾아 낼 수 있다.
java / HashMap 사용
1. 먼저 HashMap을 Map<>을 통해서 생성하자.
- HashMap의 경우 java.util.HashMap에 정의되어 있으므로 import해준다.
- Map의 경우 java.util.Map에 정의되어 있으므로 import해준다.
import java.util.HashMap;
import java.util.Map;
- HashMap은 Map 인터페이스를 구현한 클래스로, Map<>의 객체에 HashMap의 생성자로 생성되도록 할 수 있다.
- 전화번호의 경우 String문자열로 되어 있기 때문에, <String, Integer>를 키-값 쌍으로 갖는 Map을 생성한다.
- 사실상 Integer(값)는 쓸 일이 없고, Map을 활용하기 위한 것이므로, 인덱스를 넣어주겠다.
Map<String, Integer> map = new HashMap<>();
2. HashMap에 phone_book에 있는 값들을 키로, 그리고 인덱스를 값으로 넣어준다.
for(int i=0; i<phone_book.length; i++){
map.put(phone_book[i], i);
}
- 여기서 주의할 점..phone_book의 배열 크기는 .length로 얻어 올 수 있다. (c++의 size()와 헷갈리지 말자)
- map에 요소를 넣을 때는 put을 사용하고, 지정해준 키-값 쌍을 인자로 넣어주면 된다.
3. 2중 for문을 통해서 phone_book에 있는 전화번호 각각의 접두어가 HashMap에 있는지를 확인한다.
for(int i=0; i<phone_book.length; i++){
for(int j=0; j<phone_book[i].length(); j++){
if(map.containsKey(phone_book[i].substring(0,j))){
return false;
}
- 현재 가리키는 전화번호의 0부터 j번 까지의 문자열이 HashMap의 키를 통해 검색한 결과에 있으면, j번까지의 접두어로 존재하는 전화번호가 있다는 의미이기 때문에, false를 반환하도록 한다.
- 이때 사용하는 map의 함수가 containsKey()로, 검색하고자 하는 값을 인자로 넣어주면 된다.
- 자바에서 String의 substring()함수는 자르고자 하는 문자열의 시작 인덱스와 끝인덱스를 인자로 넣어주고, 만약 인자를 하나만 적는다면 해당 시작부터 끝까지 잘라준다.
- string의 쓰임같은 경우 c++에서와 헷갈리지 않도록 주의한다!!!
- 참고로 문자열의 길이를 반환할 때는 .length()이다!
이렇게 해시를 이용하면 바로바로 문자열을 map의 함수를 통해 검색할 수 있으므로 효율성에서 높아진다.
전체코드는 아래와 같다.
//해시로 풀이
import java.util.HashMap;
import java.util.Map;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Map<String, Integer> map = new HashMap<>();
for(int i=0; i<phone_book.length; i++){
map.put(phone_book[i], i);
}
for(int i=0; i<phone_book.length; i++){
for(int j=0; j<phone_book[i].length(); j++){
if(map.containsKey(phone_book[i].substring(0,j))){
return false;
}
//substring은 start index부터 end index까지
//java에서는 string size가 아니고 배열 크기는 length, 배열 안에서 문자열 길이는 length()
}
}
return answer;
}
}
반응형
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] MYSQL LV3 조건에 맞는 사용자와 총 거래금액 조회하기 / GROUP BY 이용 (0) | 2023.10.19 |
---|---|
[프로그래머스] MYSQL LV2 가격이 제일 비싼 식품의 정보 출력하기 / MAX와 서브쿼리 (0) | 2023.10.19 |
[프로그래머스] JAVA / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (1) (1) | 2023.10.18 |
[프로그래머스] MYSQL LV4 주문량이 많은 아이스크림들 조회하기 / UNION ALL 이용 (1) | 2023.10.18 |
[프로그래머스] c++ LV2 타겟 넘버 / DFS 알고리즘 사용 (0) | 2023.10.17 |