[Programmers] Lv2_전화번호 목록 (JAVA)

💻JAVA 코드 바로보기



□문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 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
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

 

🌼 JAVA 알고리즘

□초기화면

 

 

 

 

 

 

 

□풀이과정

문제분류가 해시로 되어있었지만, 우선 해시를 사용하지 않고 풀어보았다. 이중 for문을 사용해서 기준 전화번호(i)를 지정하고, 기준번호를 비교번호(j)가 포함하고 있으면 false를 반환한다.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        //접두어인 경우 찾기
        for(Integer i=0;i<phone_book.length;i++){
            String temp = phone_book[i];
            for(Integer j=0;j<phone_book.length;j++){
                if(i==j) continue;
                //System.out.println(temp+"와 "+phone_book[j]+"비교");
                if(phone_book[j].contains(temp)) return false;
            }
        }
        
        return answer;
    }
}

큰 실수가 하나 있었는데, 문제에서는 접두어인지 판별하라고 되어있으나 위의 코드처럼 contains를 사용하면 접두어가 아니어도 false체크가 된다.  예를 들어 "ff"가 기준번호이고, "aafffff"가 비교번호일 경우에는 접두어가 아니기 때문에 true를 반환해야 하지만, 위의 코드는 false를 반환한다. 따라서 indexOf를 사용하여 0일 경우(접두어일 경우)에만 false체크를 하도록 수정했다.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        //접두어인 경우 찾기
        for(Integer i=0;i<phone_book.length;i++){
            String temp = phone_book[i];
            for(Integer j=0;j<phone_book.length;j++){
                if(i==j) continue;
                //System.out.println(temp+"와 "+phone_book[j]+"비교");
                if(phone_book[j].indexOf(temp)==0) return false;
            }
        }
        
        return answer;
    }
}

테스트1과 5가 정상적으로 작동함을 알 수 있다. 하지만 후반부 테스트케이스와 효율성 테스트가 실패한걸로 보아...이런....이 풀이방법은 아닌 듯 싶다. 문제분류대로 hash를 사용해보기로 했다. 해시하면 가장 먼저 떠오르는 hashMap을 이용해보았다. 해시 알고리즘은 아래 링크 참고! 정리가 잘되어있어서 이해하기 쉽다.

 

해쉬 알고리즘(Hash Algorithm) 요약 정리, 테스트 코드

0번째부터 j번째까지 각 문자열을 잘라보고, 잘린 문자열이 해시에 존재하면 false로 처리한다.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        //HashMap
        HashMap<Integer,String> hashMap = new HashMap<>();
        for(int i=0;i<phone_book.length;i++){
            hashMap.put(i,phone_book[i]);
        }
        //각 전화번호 확인
        for (int i = 0; i < phone_book.length; i++) {
            //기준 전화번호
            for (int j = 0; j < phone_book[i].length(); j++) {
                //System.out.println(phone_book[i].substring(0,j)+"비교");
                if(hashMap.containsValue(phone_book[i].substring(0,j))){
                    return false;
                }
            }
        }
            
        
        
        return answer;
    }
}

위의 검사결과를 봤을 때, 후반 테스트케이스(아마 값이 많은 경우)로 갈수록 소요시간이 급속도로 늘어나는 것을 확인할 수 있다. HashMap에서 key와 value 두가지 값을 사용하기 때문에 소요시간이 늘어난 것 같아 value 하나의 값만 사용하는 HashSet으로 바꾸어보았다. hash하면 hashMap만 사용하던 습관이 있어서 그런지 두가지 값을 사용할 필요가 없었는데도 hashMap을 써버렸다 ㅜ

 

 

 

 

 

 

 

 

 

□완성코드

import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        //HashMap
        HashSet<String> hashSet = new HashSet<>();
        for( String value : phone_book ) {
			hashSet.add(value);
		}
        //각 전화번호 확인
        for (int i = 0; i < phone_book.length; i++) {
            //기준 전화번호
            for (int j = 0; j < phone_book[i].length(); j++) {
                if(hashSet.contains(phone_book[i].substring(0,j))){
                    return false;
                }
            }
        }
            
        
        
        return answer;
    }
}

예상대로 HashSet으로 바꾸니 소요시간이 많이 줄어들었다- 통과!

 

 

 

 

---

□링크

About Me

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