[Java : 프로그래머스] 전화번호 목록

📝 문제

https://programmers.co.kr/learn/courses/30/lessons/42577?language=java

🎯 풀이

문제 분류는 Hash로 분류되어 있지만, 자바는 Hash없이 처리가 가능하다.

자바의 String 클래스는 접두사와 접미사 관련 메소드를 지원한다.
startWith과 endWith이 그 주인공이다.
좋은 메소드를 제공하는데 굳이 어렵게 구현할 필요는 없다.
바로 사용해보자.

❌ i -> j만 비교

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

# 정확성  테스트
테스트 1 〉	통과 (0.02ms, 52.2MB)
테스트 2 〉	통과 (0.04ms, 53.2MB)
테스트 3 〉	통과 (0.03ms, 52.9MB)
테스트 4 〉	통과 (0.03ms, 51.9MB)
테스트 5 〉	통과 (0.02ms, 51.9MB)
테스트 6 〉	통과 (0.07ms, 52MB)
테스트 7 〉	통과 (0.02ms, 52.1MB)
테스트 8 〉	실패 (0.02ms, 53MB)
테스트 9 〉	실패 (0.02ms, 52.9MB)
테스트 10 〉	통과 (0.02ms, 52.7MB)
테스트 11 〉	통과 (0.03ms, 54.3MB)

# 효율성  테스트
테스트 1 〉	통과 (1.80ms, 55.9MB)
테스트 2 〉	통과 (1.35ms, 57.1MB)

으엥? 8,9번 테스트케이스에 걸린다.
반례를 생각해보자… 어떤 경우가 걸리는걸까?

반례는 생각외로 단순하다.
문자열의 길이 순으로 정렬된 배열이 아니기 때문에,
접두사가 될 수 있음에도 지나가는 경우가 생긴다.

먼저 정렬을 하고, 비교하는 방법은 어떨까?
정렬은 무조건 O(n)시간이 소요된다.
이미 O(n^2)이 돌고 있으므로, 추가적으로 루프를 돌리고 싶진 않다.
그럼 해결 방법이 무엇이 있을까?
비교 할 때 한쪽만 비교하는게 아니라 양측을 모두 비교하면 된다!

---

⭕ i <-> j 비교

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

#정확성  테스트
테스트 1 〉	통과 (0.08ms, 52.8MB)
테스트 2 〉	통과 (0.02ms, 52.7MB)
테스트 3 〉	통과 (0.03ms, 52.9MB)
테스트 4 〉	통과 (0.02ms, 52.9MB)
테스트 5 〉	통과 (0.06ms, 52.1MB)
테스트 6 〉	통과 (0.02ms, 52.4MB)
테스트 7 〉	통과 (0.02ms, 52.6MB)
테스트 8 〉	통과 (0.02ms, 52.4MB)
테스트 9 〉	통과 (0.03ms, 53MB)
테스트 10 〉	통과 (0.02ms, 54.5MB)
테스트 11 〉	통과 (0.03ms, 52.1MB)

# 효율성  테스트
테스트 1 〉	통과 (0.05ms, 57.1MB)
테스트 2 〉	통과 (0.05ms, 57.5MB)

👏👏👏👏👏