문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요
제한 사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제
| phone_book | return |
|---|---|
| ["119", "97674223", "1195524421"] | false |
| ["123","456","789"] | true |
| ["12","123","1235","567","88"] | false |
문제 단순화 하기
어떤 번호가 다른 번호의 시작과동일하면 된다!
처음 생각했던 방법은
1. 순서를 정렬
Arrays.sort();
2.제일 작은 수인 [0] 번의 배열과 전부 비교해보기
.substring(int startIndex,int endIndex);
-> startIndex(포함)부터 endIndex(불포함)까지의 문자열을 리턴
ex) str.substring(2, 4) : startIndex 2부터 endIndex 4 이전까지의 문자열을 잘라서 리턴
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Arrays.sort(phone_book);
for(int i =1;i < phone_book.length;i++){
if(phone_book[0].equals(phone_book[i].substring(0, phone_book[0].length())))
answer = false;
break;
}
return answer;
}
}이렇게 하니까 런타임 에러가 발생했다...
런타임 에러가 발생할 수 있는 원인!
- 배열에 할당된 크기를 넘어서 접근했을 때
- 전역 배열의 크기가 메모리 제한을 초과할 때
- 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
- 0으로 나눌 떄
- 라이브러리에서 예외를 발생시켰을 때
- 재귀 호출이 너무 깊어질 때
- 이미 해제된 메모리를 또 참조할 때
- 프로그램(main 함수)이 0이 아닌 수를 반환했을 때
잘 모르겠다..
먼가 코드가 잘못된거 같다
그럼? 다시 처음으로 돌아와서
Hash문제니까 hash를 사용해봐야지?
-
배열의 모든 수를 HashMap에 넣기
HashMap<String, Integer> map = new HashMap<>();
map.put(Key,Value); -
접두어가 있는지 확인하기
HashMap.containsKey(String);
-> String 이라는 key가 현재 HashMap에 있는지 확인
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
HashMap<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))){
answer=false;
}
}
}
return answer;
}
}그렇다면 여기서!
value 가 필요없는데 HashSet을 사용할순 없을까? 라는 의문이 든다.
두가지의 차이점이 무엇일까?
HashMap vs HashSet
| HashMap | HashSet | |
|---|---|---|
| 정의 | Map interface 구현체 | Set interface 구현체 |
| 데이터 저장형태 | key-value value들이 key에 mapping | 객체 그 자체를 저장 내부구현코드에서 필드로 선언한 객체(dummy 객체)를 value 값으로 사용 |
| 데이터 삽입 방법 | put() key-value형태로 저장 1개의 객체 생성 | add() 객체 자체를 저장하고, 내부적으로 HashMap을 사용 2개의 객체가 삽입 연산동안 생성 |
| 중복여부 | key 중복 허용x vaule중복 허용 o | 중복혀용 x |
| null 허용여부 | key - 단 하나의 null vaule - 여러개의 null | 단 하나의 null값 |
| 성능 | HashSet보다 빠름 | 오직 객체만 저장 가능해 HashMap보다 느림 |
