[알고리즘] 프로그래머스 > 해시 > 전화번호 목록

문제 설명

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

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

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

프로그래머스

나의 풀이 (java)

import java.util.Arrays;

public class Phonebook {

    public static void main(String[] args) {
        String[] phone_book = {"12", "123", "1235", "567", "88"};
        System.out.println("###    RESULT  : "+ solution(phone_book));
    }

    // String 정렬(12,123,1235,222,..) 후 비교
    public static 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;
    }

    // 이중 for문 사용 - 효율성 테스트에서 걸림
    public static boolean solution2(String[] phone_book) {
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book.length; j++) {
                if(i != j && phone_book[i].startsWith(phone_book[j])) return false;
            }
        }
        return true;
    }
}

풀이 방법

예전에 다른 사람의 풀이를 봤던게 어렴풋이 기억에 남아서 비슷하게 사용한 것 같다

중요 아이디어는 

• startWith : 문자열의 prefix(접두사) 확인 가능
• Array.Sort(문자) : 문자를 비교하면 1, 12, 123 이런식으로 정렬된다는 특징을 사용

다른사람의 풀이 (java) 

class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);
        boolean result = true;
        for (int i=0; i<phoneBook.length-1; i++) {
            if (phoneBook[i+1].contains(phoneBook[i])) {
                result = false;
                break;
            }
        }
        return result;
    }
}

Godd Idea : String 정렬의 특징을 이용한 비교

느낀점

• 해시를 사용하기전 Sorting을 통해 성능만 높이는게 성능을 위한 옵션이 아니라, 
  필수 사항이 되기도 한다