[프로그래머스] 전화번호 목록

1.  문제 설명

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

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

2. 제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

3. 입출력예

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

4. 풀이

Solution 1 (이중for문 => 실패)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {      
    	Arrays.sort(phone_book, new Comparator<String>(){
        @Override
        public int compare(String o1, String o2) {
            if (o1.length() > o2.length()) {
              return 1;
            } else if (o1.length() < o2.length()) {
              return -1;
            } else {
              return 0;
            }
          }
        });
    
        for (int i = 0; i < phone_book.length - 1; i++)
            for(int j=i+1; j<phone_book.length; j++)
                if (phone_book[j].startsWith(phone_book[i]))
                    return false;
            
        return true; 
    }
}

Solution 2(해시 => 성공)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {        
        Set<Integer> length = new HashSet<>();
        for(String p: phone_book) length.add(p.length());
        Integer[] y = length.toArray(new Integer[length.size()]);
        
        HashMap<String, Integer> hm = new HashMap<>();
        for(String p: phone_book) hm.put(p, 1);
        
        for(String p: phone_book){
            for(int i=0; i<y.length; i++){
                // 같은 전화번호가 중복해서 들어있지 않으므로 <= 으로 변경
                if(p.length() <= y[i]) break;
                String c = p.substring(0, y[i]);
                // 미리 HashMap에 값을 다 넣어놓고 비교!
                if(hm.containsKey(c)) return false;
            }
        }
        return true;
    }
}

5. 풀이 설명

Solution 1 (이중for문 => 실패)

처음는 쉽게 가기 위해 이중for문을 돌렸었다. 바로 효율성 탈락!

1. 이중for문을 돌릴때, 글자 크기 때문에 Exception이 발생하는 것을 막기 위하여 Comparator를 통해 글자 크기 대로 정렬

Arrays.sort(phone_book, new Comparator<String>(){
    @Override
    public int compare(String o1, String o2) {
        if (o1.length() > o2.length()) {
          return 1;
        } else if (o1.length() < o2.length()) {
          return -1;
        } else {
          return 0;
        }
      }
});

2. startsWith() 기본 함수를 활용하여 접두어 비교 - 접두어가 있는경우 바로 false 반환

if (phone_book[j].startsWith(phone_book[i])) return false;

Solution 2 (해시 => 성공)

1. phone_book에 있는 번호들의 길이가 긴 문자열을 짧은 길이의 length만큼 잘라서 접두어를 비교하기 위하여 length 를 먼저 구했다.

   그 중 중복된 값은 피하기 위하여 Set을 사용했고, Set을 Array로 바꾸기 위하여 toArray를 사용했다.

Set<Integer> length = new HashSet<>();
for(String p: phone_book) length.add(p.length());
Integer[] y = length.toArray(new Integer[length.size()]);

2. HashMap에 번호를 모두 담아 두었다.

3. 이중for문 이지만, 경우의 수를 줄여놓았고(문자열 길이들의 배열), 해시를 사용하였기 때문에 효율성에서 문제는 없었다.

    예시) 아래 처럼 되는 알고리즘이다.

HashMap	["119", "97674223", "1195524421"]
length(=y)	[ 3, 8, 10 ]
p.substring(0, length)	["119", "976", "97674223", "119", "11955244", "1195524421"]
	[패스(글자 길이가 같으므로), 패스, 패스, 걸림, 패스, 패스,]

for(String p: phone_book){
    for(int i=0; i<y.length; i++){
        // p의 length가 y배열에 있는 length보다 작으면 substring시 exception 발생
        // 같은 전화번호가 중복해서 들어있지 않으므로 = 추가
        // (만약 p=123이면 HashMap에 미리 본래의 값이 들어가 있기 때문에 넘어가야한다)
        if(p.length() <= y[i]) break;
        String c = p.substring(0, y[i]);
        if(hm.containsKey(c)) return false;
    }
}

6. 결과 

Solution 1(이중for문)

Solution 2(해시)

7. 마치며

확실히 해시가.. 매력이 있다.!!!! 

다른거 좀 하고 가족행사 다니다 보니 알고리즘을 일주일정도 못풀었었는데 굉장히 허전(?)했다.

알고리즘 너 이자식.. 내가 꼭 마스터해주마!