해시에 대한 이해를 높이기 위해 이 문제에 도전했다. 그런데 우선 나는 해시함수에 대해 모르는게 많았고 이해도 잘 못하고 있었다.
그래서 우선 문제를 풀고 다른 사람들이 풀어놓은 코드를 보면서 이해를 높이기로 하였다.
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른
번호의 점두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제
입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.
우선 나의 코드를 먼저 보자
class Solution {
public boolean solution(String[] phone_book) {
for (int i = 0; i < phone_book.length - 1; i++) {
int len = phone_book[i].length();
for (int j = i + 1; j < phone_book.length; j++) {
if (phone_book[j].length() >= len && phone_book[i].equals(phone_book[j].substring(0, len))) {
System.out.println(phone_book[j].substring(0, len)+" " +phone_book[i]);
return false;
} else if (phone_book[j].length() < len
&& phone_book[i].substring(0, phone_book[j].length()).equals( phone_book[j])) {
return false;
}
}
}
return true;
}
}나는 우선 해시함수를 사용하지 않고 풀어보았다.
각 문자열의 길이를 비교해 문제를 풀었다.
문자열 비교라 equals()함수를 사용하고, 필요 길이만큼 문자열을 자르기 위해 substring함수를 사용하였다.
문제의 의도와는 다르게 해시를 사용하지 않고 간단하게 문제를 해결하였다.
그래서 문제의 의도를 파악하기 위해 hash를 사용한 다른 분들의 코드를 참고하여 공부를 하였다.
HashMap에 대해 다룬 피드는 있지만 Map이나 Hash에 대한 내용은 흔하고 자주 다루는 기법이기 때문에 새로운 피드에서 심도 깊게 다뤄보도록 하겠습니다.
hash를 적용한 다른분의 코드를 살펴보겠습니다.
hashCode()함수를 사용하여 문제를 해결하였는데
여기서 hashCode()란 두 객체가 같은 객체인지 확인하는 메서드 입니다.
이는 equals() 와 비슷한데 차이가 있습니다. 이 차이는 다른 피드에서 심도있게 다뤄보도록 하겠습니다.
이 블로그에 가시면 equals와 hashCode에 대해 자세하게 설명되어 있습니다.!
- 참고😊nesoy.github.io/articles/2018-06/Java-equals-hashcode
Java equals()와 hashCode()에 대해
nesoy.github.io
public class Solution {
public static Boolean solution(String[] phone_book) {
for (int i = 0; i < phone_book.length - 1; i++) {
int hashPhone = phone_book[i].hashCode();
int len = phone_book[i].length();
for (int j = i + 1; j < phone_book.length; j++) {
if (phone_book[j].length() >= len
&& hashPhone == (phone_book[j].substring(0, len).hashCode())) {
return false;
} else if (phone_book[j].length() < len
&& phone_book[i].substring(0, phone_book[j].length())
.hashCode() == phone_book[j].hashCode()) {
return false;
}
}
}
return true;
}
}
출처 : https://codevang.tistory.com/290hashCode를 활용한 코드입니다.
이 블로그 운영자분의 말에 따르면 HashSet을 써도 되고 반복문을 돌리는 등 다양한 방법이 있을것 같다고 하였습니다.
HashSet이 무엇인지 알아보아야 하겠습니다.
공부를 하면 할수록 모르는게 계속 늘어나네요 ㅠ 모르면 궁금해서 다 찾아볼 수 밖에 없긴하지만,,
그리고 인터넷에서 가장 많이 보이는 답안이라고 하는 코드를 가지고 왔습니다.
class Solution {
public boolean solution(String[] phoneBook) {
for(int i=0; i<phoneBook.length-1; i++) {
for(int j=i+1; j<phoneBook.length; j++) {
if(phoneBook[i].startsWith(phoneBook[j])) {return false;}
if(phoneBook[j].startsWith(phoneBook[i])) {return false;}
}
}
return true;
}
}저는 또 궁금한게 생겼네요
startsWith 매서드도 공부해야겠습니다..
이런 방법도 있다~ 하고 우선은 넘어가겠습니다..ㅠ
또 다른 방법으로는 올므차순 정렬을 먼저 한 뒤 앞뒤로 비교하는 방법입니다.
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++) {
if(phone_book[i+1].startsWith(phone_book[i])){
answer = false;
break;
}
}
return answer;
}
}이것도 인지만 하고 넘어가겠습니다,,
위 방법들 말고도 아주 다양한 해결책들이 있는 것 같다. 다양한 사람들의 풀이를 보고 견문을 넓히면 더 좋을 것 같다!!
추가
hash보다 startWith가 더 좋다 하니 한번 자세히 알아봐야겠습니다!!!
출처😊
blog.naver.com/PostView.nhn?blogId=travelmaps&logNo=220931531769&redirect=Dlog&widgetTypeCall=true
