해시, 전화번호 목록

✍ 레벨 2 의 전화번호 목록 문제 / 프로그래머스

 

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

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

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

 

 

맨 앞 문자열이 다른 번호의 접두어인가? 를 체크하는 문제

 

  public static boolean solution (String[] phone_book) {
        boolean flag = true;
        Arrays.sort(phone_book);
        // 정렬
        // System.out.println(Arrays.toString(phone_book));

        for (int i = 0 ; i < phone_book.length; i ++ ){
            for (int j = i+1; j < phone_book.length; j ++ ){
                if (phone_book[j].indexOf(phone_book[i]) > -1) {

                    System.out.println(phone_book[j]);
                    System.out.println(phone_book[i]);

                    return false;
                }
            }
        }
       return flag;
   }
   
   ** 이렇게 풀었더니, 실패했따. 테스트 13, 테스트 14 / 효율성 3, 4

 

☁ 효율성에서 떨어지는 이유는 Arrays.sort를 사용하는 것 + 이중 포문을 돌고 있는 중에 break를 거는 분기가 하나 더 있어야 한다고 생각한다.

 

처음에 : 

      for (int i = 0 ; i < phone_book.length; i ++ ){
           for (int j = i+1; j < phone_book.length; j ++ ){
               if (phone_book[j].indexOf(phone_book[i]) > -1) {
                   flag = false;
                   break;
               }
           }
       }

 

☁ 이 방식으로 처리하면, 문제는 테스트 케이스에서  Arrays.sort 한것보다 5개는 더틀렸다.

 

☁ Arrays.sort 는 왜 효율성이 떨어질까? 왜 테스트 케이스를 5개는 더맞을까?  내부에서 이중포문으로 도는 건 다 마찬가지 아닌가?

 

☁ 정렬도 정렬이지만 중간에 나온 숫자도 다른 번호 ( 앞에서 나왔던? ) 번호의 접두사에 해당하는 경우가 존재해서 이지 않을까 생각했다. 

 

테스트 케이스 13,14 는 제치고 효율성부터 통과하기로 했다. 

 

Arrays.sort 대신에  Collections.sort(Arrays.asList(phone_book)); 를 써봤는데 

마찬가지다.

 

이중 포문 포기해야함.

런타임 에러.

 

스트링 정렬?

 

 

 

 

 

 

맨 뒤에 숫자가 맨 처음 숫자의 접두사로 될 수 있으니까. 

 

맨 처음 숫자는 고정이라는 말이 문제에 없었으니까.. 

 

정렬부터

미련하게 아무 생각없이 Integer로 정렬하지 말자 숫자는 0에서부터 시작한다.

Integer 타입으로 정렬하지 말 것.

 

 

 

✍ 결국 String 으로 정렬해서 비교 하되, 앞뒤 스트링간의 비교를 추가했다. 

☁ Arrays.sort 나 Collections.sort 는 속도 차이가 크게 차이가 나는 것 같지는 않다 정말 큰 컬렉션을 돌리는것이 아니라면? 시간은 나중에 비교해보거나 찾아보자. 

 

✍ 반복문을 2번 이상 돌리지 않는 게 키 포인트인 것 같다. 

 

✍ 시간복잡도라는 개념이 왜 중요한지 다시 한 번 생각해보자.

 

  public static boolean solution (String[] phone_book) {
        boolean flag = true;
        Arrays.sort(phone_book);

        for (int k = 1; k < phone_book.length-1 ; k ++ ) {

            String mid = phone_book[k];
            String bef = phone_book[k-1];
            String aft = phone_book[k+1];
           // System.out.println(" mid :: "+mid +" / bef :: " + bef) ;

            if ( mid.startsWith(bef) || mid.startsWith(aft) || bef.startsWith(mid) || aft.startsWith(mid)) {
                return false;
            }
        }
        return flag;
    }

 

✍ 마지막으로, 테스트는 통과했지만 운이 좋아서 통과한 정답 일 수 있다.