$$config title: [문제해결]❓ 해시 - 전화번호 목록 keywords: - IT - 프로그래머스 $$ # 관련 링크 - 문제풀이 종합 [https://slog.gg/b/4715](https://slog.gg/b/4715) [GIT](https://github.com/donhyuck/algorithm/commit/cf664fc04237b5d08ab59d6a7edeb43fe3180d98) ### 문제설명 - 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. ``` 구조대 : 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입니다. ### 내가 생각한 풀이방법 1 . 일단, 문자열의 포함여부로 접근 2 . 루프내에서 자신은 빼고, 나머지 항목에 포함되는지 확인 ```java class Solution { public boolean solution(String[] phone_book) { boolean answer = true; for (int i = 0; i < phone_book.length - 1; i++) { for (int j = 1; j < phone_book.length; j++) { if (!phone_book[i].equals(phone_book[j]) && phone_book[j].contains(phone_book[i]) || phone_book[i].contains(phone_book[j])) { return false; } } } return answer; } } ``` 3 . 하지만 실패가 확인되었고, 살펴보니 contains는 위치상관없이 포함여부에 대한 확인이라서 전화번호의 접두어가 중복되는지 확인하기 위해 startWith사용 결과적으로 겹치는 경우가 아니면서 특정 문자열로 시작하는 경우 false리턴 - 하지만 테스트케이스는 전부통과하였지만, 효율성테스트에서 **시간초과** 로 실패 ```java class Solution { public boolean solution(String[] phone_book) { boolean answer = true; for (int i = 0; i < phone_book.length; i++) { for (int j = 0; j < phone_book.length; j++) { if (!phone_book[i].equals(phone_book[j]) && phone_book[i].startsWith(phone_book[j])) { return false; } } } return answer; } ``` 4. 정렬 후 반복문으로 검사 `Arrays.sort(phone_book);` - sort를 하는 이유? : 정렬을 통해 접두사 부분이 비슷한 문자열들을 차례대로 나열하게되고 이렇게 될 시 바로 앞의 숫자와 뒤의 숫자를 비교함으로써 문제를 해결할 수 있기때문. - 이후 i번째의 다음 값과 비교 ### 내풀이 ```java package hash.phoneBook_List; import java.util.Arrays; public class Solution { public static void main(String[] args) { Solution test = new Solution(); boolean testResult; // 테스트1 String[] intputArray1 = new String[] { "119", "97674223", "1195524421" }; testResult = test.solution(intputArray1); System.out.println("Test 1 : " + testResult); // 테스트2 String[] intputArray2 = new String[] { "123", "456", "789" }; testResult = test.solution(intputArray2); System.out.println("Test 2 : " + testResult); // 테스트3 String[] intputArray3 = new String[] { "12", "123", "1235", "567", "88" }; testResult = test.solution(intputArray3); System.out.println("Test 3 : " + testResult); } public boolean solution(String[] phone_book) { // 정렬로 효율성증가 Arrays.sort(phone_book); // 다음 항목과 비교하여 접두어 확인 for (int i = 0; i < phone_book.length - 1; i++) { if (phone_book[i + 1].startsWith(phone_book[i])) { return false; } } return true; } } ``` ### 다른 사람의 풀이 - 해시맵을 이용한 풀이 ```java class Solution { public boolean solution(String[] phoneBook) { Map map = new HashMap<>(); for (int i = 0; i < phone_book.length; i++) { map.put(phone_book[i], i); } for (int i = 0; i < phone_book.length; i++) { for (int j = 0; j < phone_book[i].length(); j++) { if (map.containsKey(phone_book[i].substring(0, j))) { return false; } } } return true; } } ``` ### 보완 - 효율성검사도 있어서 단순히 통과만 한다고 끝이 아니라는 것을 느꼈다.

게시글 상세