(알고리즘 스터디) 4주차 월 _ 해시🔐 _ (Programmers) 전화번호 목록

🌟 프로그래머스 / 해시 / Level2 / 전화번호 목록

📃 문제

프로그래머스

🚫 제한 사항

• 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️⃣ 단순 배열 전체 탐색을 통한 풀이

① 구현 과정

➡️ 단순 배열 탐색을 통해서 하나씩 비교하는 방식으로 코드를 짜보았다. 생각해볼점은 두가지 였다.

1. 문자열을 비교하는 법

➡️ String 내부 함수 중 substring() 함수를 활용하기로 했다.

// 예시
String abc = "abc"
String a = abc.substring(0,1);
String bc = abc.substring(1);

 

2. 배열을 문자열의 길이를 기준으로 정렬하는 법

➡️ 1 에서 정한 substring() 을 이용하려면 배열을 문자열의 길이를 기준으로 정렬할 필요가 있었다. 단순 Arrays.sort() 를 활용하면 (1) 문자열의 맨 앞자리  (2) 문자열의 길이 순으로 분류되어 index 오류가 발생하므로 원하는 형태가 아니였다.

예시) [12, 124, 89, 3456, 72]
[12, 124, 3456, 72, 89] // 단순 Arrays.sort() 활용시
[12, 89, 72, 124, 3456] // 내가 원하는 형태 (문자열이 길이순)

레퍼런스를 찾아보니 Arrays.sort() 함수의 내용중 첫번째 인자로 배열, 두번째 인자로 Comparator 를 넘겨주는 방법이 있었다. Comparator 사용 방법을 잘 몰라서 검색해보니 아래와 같이 Overriding 을 통해서 구현 가능헀다.

Arrays.sort(phone_book, new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
});

② 구현 코드

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        // 정렬 (문자열 길이 순)
        Arrays.sort(phone_book, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        });
        
        // 탐색
        for (int i=0; i<phone_book.length; i++) {
            String pre = phone_book[i];
            int preSize = pre.length();
            for (int j=i+1; j<phone_book.length; j++) {
                String comp = phone_book[j];
                if (pre.equals(comp.substring(0, preSize))) {
                    return false;
                }
            }
        }
        return answer;
    }
}

③ 결과

➡️ 일반 코드들은 모두 통과했지만 효율성 테스트에서 2개를 통과하지 못했다.

➡️ 숫자비교를 위해 형변환을 시도해보았지만, 반대로 형변환 후 풀이 시 더 오래걸렸다.

2️⃣ Hash Set 사용

➡️ Hash 에 개념에 대해 좀 더 정리해보고나니 검색과정에서 Hash 관련 자료구조를 사용하는 것이 얼마나 효율적인지 알 수 있었다.

① 풀이 코드

import java.util.Set;
import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        // Set 생성 및 원소 추가
        Set<String> set = new HashSet<>();
        for (String str : phone_book) {
            set.add(str);
        }
        
//         // 탐색 (1) ➡️ 시간초과
//         for (int i=0; i<phone_book.length; i++) {
//             String prefix = phone_book[i];
            
//             for (String str : set) {
//                 if (str.equals(prefix)) {
//                     continue;
//                 }
//                 if (str.startsWith(prefix)) {
//                     return false;
//                 }
//             }
//         }
        
        // 탐색 (2)
        for (String str : set) {
            for (int i=1; i<str.length(); i++) {
                if (set.contains(str.substring(0,i))) {
                    return false;
                }
            }
        }
        return answer;
    }
}

➡️ 탐색 (1) 의 방식은 문자열을 비교하는 equals() 메서드 때문에 효율성이 떨어졌다.

➡️ 탐색 (2) 의 방식은 빠르게 탐색이 가능했다.

 

② 결과

➡️ 이전에 실패했던 테스트 3&4 도 잘 통과하였다.

💻 풀이 코드

[level 2] Title: 전화번호 목록, Time: 367.90 ms, Memory: 189 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@defe7e

🔗 참고

① Java Array Sorting 배열 정렬 (https://velog.io/@alicesykim95/Java-Array-Sorting-%EB%B0%B0%EC%97%B4-%EC%A0%95%EB%A0%AC)