[프로그래머스] 해쉬 - 전화번호 목록

📌 전화번호 목록

📕 문제

문제 설명

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

• 구조대 : 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입니다.

---

알림

2019년 5월 13일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

🙄 문제 설명

이 문제는

1. phone_book[] 안에 있는 어떤 value가 다른 value의 접두어를 가질때 return false
2. 어떤 value도 다른 value의 접두어가 아니면 return true

위의 조건만 성립하면 된다.

Hash 문제이긴 하나 2중 for문으로 풀어도 효율성 테스트를 통과한다.

🥕 나의 풀이

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        String str = "";

        for(int i = 0; i < phone_book.length; i++){
            for(int j = 0 ; j < phone_book.length; j++){
                if(phone_book[i].length() > phone_book[j].length() && i != j)
                    continue;
                str = phone_book[j].substring(0, phone_book[i].length());
                if(phone_book[i].equals(str)){
                    return false;
                }
            }
        }
        return answer;
    }
}

2중 for문으로 풀었다. 효율적이지 않다는걸 알지만 알고리즘 문제들을 풀면서 문제를 푸는 시간과 효율성 사이의 기회비용을 생각해야 한다고 느꼇기 때문에 이전에 hash로 풀다가 포기한걸 다시 2중 for문으로 풀었다.

접근법은 간단했다.

1. i번째의 str을 접두어로 잡는다.
2. j번째는 str을 비교 대상으로 잡는다.
3. i번째 str과 j번째 str의 length와 자기 자신이 아닌 경우를 제외한다.
4. i번째 str의 length만큼 j번째 str을 잘라준 후, 같은지 비교한다. (접두어 비교)
5. 같으면 return false
6. 모두 탐색해도 안되면 return true

효율성 테스트는 2ms ~ 3ms 정도 나왔다.

재밌는건, 처음에 sort를 해서 가장 length가 작은 수 부터 비교해 비교 시간을 조금이라도 줄이려고 했으나, 효율성 테스트를 통과할 정도 이긴 해도 20ms 정도의 성능을 보여주었다. sort가 엄청나게 많은 자원을 잡아 먹는다는걸 알고는 있었지만 이정도 일 줄은 몰랐다. 잘 생각해서 사용하도록 해야겠다.

🥕 다른 분의 풀이

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

String.startwith(str) 이 함수를 여기서 처음 알게 되었다.

코테를 풀면서 느끼는 거지만 java에서 기본적으로 제공해주는 유용한 함수들을 많이 배우는것 같다. 위의 코드로 효율성 테스트를 돌렸을때 0.8ms 정도의 성능을 보여주었다. 제일 효율적이고 간단한 코드 인 것 같다.