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

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

프로그래머스

 

문제는 해시문제라고 분류되어 있는데 굳이 해시로 풀 필요가 없는 것 같아서 해시로 풀지 않았습니다. 

혹시 해당 문제를 해시로 푸는 것이 더 좋다! 의 이유를 안다면 설명 plz..

처음 생각한 방법은, 주어진 배열을 길이 순으로 정렬하여서 뒤에 있는 값들을 다 비교하도록 했는데 이럴 경우 이중포문이 되어서 시간 초과가 발생했습니다. 

-> 정렬 예시 : [12, 88, 123, 134, 567, 1235]

package yejin.song;

import java.util.Arrays;
import java.util.Comparator;

public class PGS_전화번호목록 {
    public static void main(String args[]){
        System.out.println(solution(new String[]{"12","123","1235","567","88","134"}));
    }
    public static boolean solution(String[] phone_book) {

        Arrays.sort(phone_book, Comparator.comparing(String::length));
        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].startsWith(phone_book[i])) return false;
            }
    }
        return true;
}

 

 

배열을 길이 순이 아니라 사전 순으로 정렬하면 바로 뒤에 있는 값 하나만 비교해도 되어서 이중포문 없이 통과 가능합니다 ! 

-> 정렬 예시: [12, 123, 1235, 134, 567, 88]

package yejin.song;

import java.util.Arrays;

public class PGS_전화번호목록 {
    public static void main(String args[]){
        System.out.println(solution(new String[]{"12","123","1235","567","88","134"}));
    }
    public static boolean solution(String[] phone_book) {

        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length; i++){
            if(phone_book[i+1].startsWith(phone_book[i])) return false;
        }
        return true;
    }
}