자바 - 프로그래머스 / 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

lv2

 

구현 방법

조건

 - phone_book의 길이는 1 이상 1,000,000 이하입니다.
 - 각 전화번호의 길이는 1 이상 20 이하입니다.
 - 같은 전화번호가 중복해서 들어있지 않습니다.

 

효율성 테스트 실패 방법

1. phone_book을 문자열 길이 오름차순으로 정렬한다. 시간복잡도 - 평균 : O(nlog(n)) / 최악 : O(n^2)

2.  phone_book 문자열 하나와 그 외 phone_book 문자열들을 비교하여, 한 번호가 다른 번호의 접두어인지 확인한다

    (이중 포문 사용). 시간복잡도 -  O(n^2)

 

phone_book 길이가 1000000이라서 당연히 효율성 테스트에서 하나도 통과하지 못했다. 그래서 2번 방법에서 answer가 false인 경우, break를 걸어 이중 포문을 나가는 경우를 추가 했다. 하지만 그렇게 해도 최악의 경우 시간 복잡도는 O(n^2)으로 같아서 효율성 테스트 3, 4번은 통과 못했다. 

 

효율성 테스트 성공 방법

결국 시간 복잡도 O(n^2)을 O(n)으로 낮추어야 된다. 값을 찾을때 시간 복잡도를 낮출수 있는 방법은 해시를 이용하는 방법이 있다. 

1.phone_book을 원소로 HashSet을 만든다. 시간복잡도 - O(n)

2. phone_book의 원소 하나를 꺼내서 원소를 원소의 길이를 첫 문자 기준으로 1 ~ (문자 길이 - 2)까지 나누어서 HashSet에 포함 되어 있는지 확인한다. 여기서 주의 할 점은 원소 자체와 HashSet에 원소가 포함되어 있는지는 체크 하면 안되기 때문에 마지막 문자 길이 - 2가 되어야 한다. 시간복잡도 - O(n)

 

코드

효율성 테스트 실패 방법 1

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Arrays.sort(phone_book, (p1, p2) -> {
            return p1.length() - p2.length();
        });
    
        for(int i = 0; i < phone_book.length; i++) {
            for(int j = i + 1; j < phone_book.length; j++) {
                if(phone_book[i].equals(phone_book[j].substring(0, phone_book[i].length())))
                    answer = false;
            }
        }
        
        return answer;
    }
}

효율성 테스트 실패 방법 2

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        
        
        Arrays.sort(phone_book, (p1, p2) -> {
            return p1.length() - p2.length();
        });
    
        for(int i = 0; i < phone_book.length; i++) {
            for(int j = i + 1; j < phone_book.length; j++) {
                if(phone_book[i].equals(phone_book[j].substring(0, phone_book[i].length())))
                    answer = false;
            }
            if(!answer)
                break;
        }
        
        return answer;
    }
}

 

효율성 테스트 성공 방법

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

class Solution {
    public boolean solution(String[] phoneBook) {
        boolean answer = true;
        Set<String> pb = new HashSet<>();
        
        for(String s : phoneBook) {
            pb.add(s);
        }
        
        for(String s: phoneBook) {
            for(int i = 1; i < s.length(); i++) {
                if(pb.contains(s.substring(0, i))) {
                    answer = false;
                    break;
                }
            }
            if(answer == false)
                break;
        }
        
        return answer;
    }
}

 

느낀 점

시간 복잡도 체크하고 문제 풀자