프로그래머스 레벨 2 - 코딩테스트 고득점kit 해쉬 : 전화번호 목록[자바]

문제

난이도 : 레벨2

문제 :

• 전화번호부에 적힌 전화번호 중 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하고 결과에 따라 true, false를 리턴하는 문제.
• 전화번호는 String[] phoneBook형태로 주어지게 된다.

제한사항 :

• 1 <= phone_book <= 1,000,000
• 각 전화번호의 길이는 1이상 20이하
• 중복되는 전화번호는 없음

답

제가 처음 생각한 것은 배열을 정렬한 뒤 가장 작은 수를 가진 배열의 원소를 기준으로 다른 원소들과 비교하여 접두어에 속하는지 판단하는 것이었습니다. 

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        ArrayList<Integer> phone_save_list = new ArrayList<Integer>();
        // 전화번호 배열을 arraylist 형태로 넣은 뒤 정렬한다.
        for(String phone_num : phone_book) {
            int phone_num_integer = Integer.parseInt(phone_num);
            phone_save_list.add(phone_num_integer);
    	}
    
    	Collections.sort(phone_save_list);

    	// 첫번째에 있는값(최소값)의 각 자리 수가 배열 중에 겹치는지 체크
        Map<Integer, String> first_phone_map = new HashMap<Integer, String>();
        int[] first_phone_num;

        for(int i=0; i<phone_save_list.size(); i++) {
          String[] phone_save_num = Integer.toString(phone_save_list.get(i)).split("");
          Map<Integer, String> phone_map = new HashMap<Integer, String>();
          for(int j=0; j<phone_save_num.length; j++) {
            if(i==0) {
                first_phone_map.put(j, phone_save_num[j]);
            } else {
                phone_map.put(j, phone_save_num[j]);
            }
          }

          if(!phone_map.isEmpty()) {
            int true_count = 0;
            for(int j=0; j<first_phone_map.size(); j++) {
                if(first_phone_map.get(j).equals(phone_map.get(j))) {
                    true_count++;
                }
            }
            if(true_count == first_phone_map.size()) {
                return false;
            }
          }
        }
        return true;
    }
}
// 코드만 봐도 알것 같지만 당연히 통과 못했다..

가장 큰 문제는 자바 문법에 대한 무지였습니다. 먼저 정렬을 위해 ArrayList객체를 생성하고 배열에서 값을 옮겼습니다. 그냥 배열 형태에서도 정렬을 할 수 있다는 사실을 후에 알았습니다.

어찌저찌 Integer로 형변환 후 첫번째에 있는 값(가장 작은 값)과 나머지 값들의 비교를 위해 first_phone_map이라는 map 객체를 만들었습니다. 해쉬맵 객체에는 {자리의 위치 = 위치에 대한 값} 형태로 값을 저장하였습니다. 예를 들어, 119는 {1 = 1, 2 = 1, 3 = 9}

그리고 나머지 배열의 값들에 대해서는 phone_map이라는 객체를 또 생성하여 똑같이 {자리의 위치 = 위치에 대한 값} 을 넣어주었습니다.

자리의 위치와 값을 모두 알고 있으니 각 전화번호를 비교하여 key, value값이 첫번째 값과 전부 같으면 접두어가 된다는 의미였고 세번째 for문은 그것을 비교하는데 사용했습니다.

당연히 예상한 결과였겠지만 효율성 측면에서도 떨어지는 코드였고 예상치 못한 오류를 발견할 수 있었습니다. 전화번호 자리수가 같은 값에 대한 배열을 신경쓰지 못한 것입니다. 예를 들어, ['123', '1234, '3456', '223344'] 와 같이 최소값이 3자리인 배열에서는 최소값인 '123' 과 나머지 전화번호를 비교하여 올바른 답을 도출할 수 있었으나 ['123','124','1245'] 와 같이 최소값과 그 다음값의 자리수가 똑같을 경우 기준값인 123만 가지고 비교하니 124와 1245가 접두어임에도 불구하고 반대의 결과를 도출했습니다.

이부분에 대해서 서치했을때 답안에서는 String상태의 배열을 그대로 sort한 뒤 앞자리 수와 뒷자리 수만 비교하여 비교적 간단한 알고리즘으로 풀이한 것을 알 수 있었습니다.

Arrays.sort(phoneBook);
// 2. 1중 Loop을 돌며 앞 번호가 뒷 번호의 접두어인지 확인한다.
for (int i = 0; i < phoneBook.length - 1; i++) {
    if(phoneBook[i+1].startWith(phoneBook[i])) {
        return false;
    }
}

엥? 앞이랑 뒤에 값만 가지고 접두어 판단이 된다고? 라는 생각을 했습니다.
하지만 Integer형의 값과 String형의 값은 sorting 순서가 다르다는 것을 알 수 있었습니다. 예를 들어 [123,1234.124]의 경우 Integer형은 숫자의 크기 순서인 123->124->1234가 되지만 String형은 각 자리 수를 기준으로 비교하기 때문에 123->1234->124가 됩니다.

그래서 접두어를 판단하는데에 문제가 없었습니다. 더불어, startWith() 함수와 단순배열에서 Arrays.sort()를 사용하여 sort하는 것을 알았습니다. 

두번째 방법으로는 본 문제의 출제자가 의도했던 해시 함수를 사용하여 해결하는 것이었습니다. 

import java.util.*;
class Solution {
    public boolean solution(String[] phoneBook) {
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < phoneBook.length; i++) 
            map.put(phoneBook[i], i);
        
        for (int i = 0; i < phoneBook.length; i++)
            for (int j = 0; j < phoneBook[i].length(); j++) {
                if (map.containsKey(phoneBook[i].substring(0, j)))
                    return false;
            }
        return true;
    }

}

HashMap에 각 전화번호에 대한 값들을 넣습니다. 전화번호는 중복되지 않는다는 점을 이용하여 Key값에 넣어줍니다.

그리고 각 전화번호와 전화번호의 글자들을 쪼개어 값이 포함되어 있는지를 검사합니다.
예를 들어, ['119','112435','345] 라는 배열이 있다면
1, 11, 119
1, 11, 112, 1124, 11243, 112435
3, 34, 345

순서대로 substring한 값을 맵에 들어있는 키 값과 대조하는(containsKey) 방법입니다. 효율성 면에서 아무래도 이중 for문을 돌리니 sorting하는 방법보다 효율성이 떨어질 것 같긴 하지만 출제자가 의도한 것과 가까운 답안이라고 생각합니다. 

참고풀이
https://coding-grandpa.tistory.com/77