[프로그래머스 알고리즘 고득점 Kit][해시][Java] 전화번호 목록

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

프로그래머스

1. 틀린 코드

문자열을 사전순으로 정렬하면 접두사는 바로 옆에 있게됨

그러면 바로 옆만 비교하면서 접두사인지 아닌지 체크하고 있으면 바로 false 

return 안되고 반복문 탈출하면 true

뭐가 틀렸을까...?

아 바본가..

        Arrays.sort(phone_book, (s1, s2) -> {
            return s1.length() - s2.length();
        });

처음엔 문자열 길이가 짧은 거를 긴거랑 다 비교하면 되지 않을까 생각하고 위처럼 정렬했다.
번호의 수가 100만개인데 O(N^2) 의 시간복잡도라 다른 방법을 고민해야했다.
그렇게 사전순 배열을 떠올리고 코드를 썼지만 첫글자만 비교 정렬해버렸다.

 

아래처럼 정렬하면 문자열 전체 사전순이 아니라 맨 첫글자만 사전순이 된다...

import java.io.*;
import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        int phone_book_len = phone_book.length;
        Arrays.sort(phone_book, (s1, s2) -> {
            return s1.charAt(0) - s2.charAt(0);
        });
        for(int i=0; i<phone_book_len-1; i++){
            if(phone_book[i+1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
}

 

2. 정답 코드

 

내가 의도한 사전순 정렬로 바꾸고 정답.

import java.io.*;
import java.util.*;

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

문자열 배열 사전순 정렬

Arrays.sort(phone_book);
사전순 반대

Arrays.sort(phone_book,Collections.reverseOrder());

Arrays.sort(phone_book, (s1, s2) -> {

return s2.compareTo(s2);

};