프로그래머스 레벨 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하는 방법보다 효율성이 떨어질 것 같긴 하지만 출제자가 의도한 것과 가까운 답안이라고 생각합니다.