전화번호 목록

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

처음에는 글자 길이로 정렬을 해야 하나 싶어서 PriorityQueue 를 사용하고

class Text
{
	String content;
    int len;
}

도 따로 만들어서 풀어보다가 이렇게 구현하지 않아도 되겠구나 싶었다
글자가 맞아 떨어지는 번호들은 정렬하면 길이가 긴게 뒤에 온다
글자가 중간에 다르면 당연히 길이가 짧은게 나올 수 도 있다. 예외처리 해야한다

"123"
"1234"
"12345"
"14"
"143"
"1431"

그리고 비교를 여러번 할 필요도 없다 앞뒤로 한번씩만 비교하면 된다. 시간복잡도를 줄일 수 있다

1차 구현 통과 0~9 로 시작하는것끼리 그룹을 지어서 처리하였다

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        ArrayList<ArrayList<String>> arr = new ArrayList<ArrayList<String>>();
        for(int i = 0; i < 10; ++i)
            arr.add(new ArrayList<String>());
        
        for(int i = 0; i < phone_book.length; ++i)
        {
            String cur = phone_book[i];
            Character c = cur.charAt(0);
            int groupId = Integer.parseInt(c.toString());
            arr.get(groupId).add(cur);
        }
        
        for(int i = 0; i < arr.size(); ++i)
        {
            ArrayList<String> temp = arr.get(i);
            Collections.sort(temp);
            
            for(int j = 0; j < temp.size()-1; ++j)
            {
                String left = temp.get(j);
                int k = j+1;
                String right = temp.get(k);
                
                if(left.length() > right.length())
                    continue;
                
                right = right.substring(0, left.length());
                    
                    //System.out.println(left);   
                if(left.equals(right))
                   return false;
            }
            
            
        }
   
        
        return answer;
    }
}

2차구현 그룹없이 처리함

시간복잡도는 정렬하는 비용 O(N logN)
비교하는데 드는 비용 O(N)
합쳐서
O(N logN + N)

이다.
가장 큰 항목만 남기면
O(N * logN) 이다.

비교하는 부분의 시간 복잡도는 O(N)인데, 이는 전체 시간 복잡도에 큰 영향을 미치지 않습니다. 따라서 이 솔루션의 전체 시간 복잡도는 O(N * logN)으로 정렬하는데 들어가는 비용이 가장 큽니다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        ArrayList<String> arr = new ArrayList<>();
       
        for(int i = 0; i < phone_book.length; ++i)
        {
            String cur = phone_book[i];
            arr.add(cur);
        }
        
        Collections.sort(arr);

        for(int i = 0; i < arr.size()-1; ++i)
        {
            String left = arr.get(i);
            int j = i+1;
            String right = arr.get(j);
                
            if(left.length() > right.length())
                    continue;
                
            right = right.substring(0, left.length());
                      
            if(left.equals(right))
                  return false;
        }
  
        return answer;
    }
}

3차 리팩토링하였다

import java.util.*;

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

        Arrays.sort(phone_book);

        for(int i = 0; i < phone_book.length-1; ++i)
        {
            String left = phone_book[i];
            String right = phone_book[i+1];
                
            if(left.length() > right.length())
                    continue;
                
            if(right.startsWith(left))
                return false;
        }
  
        return answer;
    }
}