[프로그래머스/java] 전화번호 목록 (문자열 비교 - hashCode) *2021 첫 글*

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

 

---

문제의 핵심은 다른 해시 문제들과 마찬가지로 "다량의 반복적인 문자열 비교가 필요하다"입니다. 문자열을 비교하는 가장 빠른 방법중의 하나가 Hash 기법이고, 그냥 쌩으로 equals()나 startWith()를 사용하는 것은 노가다 문자열 비교입니다. 제가 알기로 해당 메소드에 해싱 기법이 들어가지는 않는 것으로 알고 있습니다. 알고리즘에서 문제에서 "노가다 문자열 비교 작업"이 필요하다면 해시를 먼저 떠올리는 것이 좋을 듯합니다.

 

출처 : codevang.tistory.com/290

---

 

 

• 해시코드(HashCode)를 이용한 방법
  • 이중 반복문을 사용하여 문자열 모두 2개씩 비교

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        // 이중 반복 통해 문자열 두개씩 비교
        for(int i = 0; i < phone_book.length - 1; i++) {
            int hashPhone = phone_book[i].hashCode(); // 각 문자열의 해시코드(숫자) 구하기 (마지막 문자 제외)
            int size = phone_book[i].length();
            
            for(int j = i+1; j < phone_book.length; j++) {
                if(phone_book[j].length() >= size && 
                   hashPhone == (phone_book[j].substring(0, size).hashCode())) { // 앞 문자열보다 뒤 문자열 길이가 같거나 더 길고 & 앞 문자열의 해시코드와 뒤 문자열의 앞 문자열 길이만큼의 해시코드가 같으면
                   return false; // 앞 문자열을 뒤 문자열이 접두사로 포함하고 있다는 의미이므로 false 리턴
                } else if(phone_book[j].length() < size &&
                         phone_book[i].substring(0, phone_book[j].length()).hashCode() == phone_book[j].hashCode()) // 앞 문자열보다 뒤 문자열 길이가 더 작고 & 앞 문자열에서 뒤 문자열의 길이만큼 자른 부분의 해시코드와 뒤 문자열의 해시코드가 같으면
                    return false; // 뒤 문자열을 앞 문자열이 접두사로 포함하고 있다는 의미이므로 false 리턴
            }
        }
        
        return answer; // 두개씩 비교해서 없으면 true 리턴
    }
}

 

 

 

 

• startsWith() 함수 이용 방법

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;
    }
}

 

 

 

---

 

• 이 문제는 둘의 속도가 비슷하나 해시코드 비교의 경우 중복 연산을 제거해주기 때문에 중복 연산이 필요한 문제라면 더 빠른 속도를 낼 수 있다!