99클럽 코테 스터디 5일차 TIL 전화번호 목록

📝 문제

프로그래머스

 

🔥 시도해본 접근 방식

1. 선형탐색

문제에 제한조건을 보고 탐색을 해야 하긴 하지만 효율성을 위해

길이가 짧은 문자열부터 오름차순으로 배열을 정리한 후에 탐색을 해야겠다고 생각하고 접근하였다.

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

class Solution {
    public boolean solution(String[] phone_book) {
        // 전화번호의 길이는 1~20 이고
        // 배열의 길이는 1 ~ 1,000,000 이므로
        // 효율적인 탐색을 위해 배열을 전화번호 길이의 오름차순으로 정렬
        Arrays.sort(phone_book, Comparator.comparingInt(String::length));

        // 배열의 첫번째 원소부터 순차적으로 다른 원소들의 접두어인 경우가 있는지 탐색 하고
        // 있다면 false 를 리턴
        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;
                }
            }
        }

        // 한 번호가 다른 번호의 접두어인 경우가 없다면 true 리턴
        return true;
    }
}

정확성 테스트는 통과하였지만 효율성 테스트에서 실패해서 어떻게 효율성을 개선할까 고민하다가 

접두어로 가지고있을 원소(= phone_book[j])를 길이가 긴 순서부터 탐색하면 효율성이조금 개선될것 같다고 생각했고

반복문 부분을 다음과 같이 수정했다.

// 효율성을 위해 길이가 가장 짧은 원소를 길이가 가장 긴 원소부터 내림차순으로 탐색을 한다.
// 한 번호가 다른 번호의 접두어인 경우가 있다면 false 를 리턴
for (int i = 0; i < phone_book.length; i++) {
    for (int j = phone_book.length - 1; j >= i + 1; j--) {
        if (phone_book[j].startsWith(phone_book[i])) {
            return false;
        }
    }
}

그러나 미미한 시간 개선은 있었으나 똑같이 실패해였다.

오래 고민해본결과 코드에 비효율적인 연산이 들어있는 것을 깨달았다.

 

✨ 성공 코드

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        // 효율적인 탐색을 위해 배열을 정렬
        Arrays.sort(phone_book);

        // 위에서 정렬을 했으므로 붙어있는 원소끼리만 비교하면 
        // 한 번호가 다른 번호의 접두어인 경우가 있는지 여부를 알 수 있음 
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;
            }
        }

        // 한 번호가 다른 번호의 접두어인 경우가 없다면 true 리턴
        return true;
    }
}

우선 sort()에 정렬 정책을 따로 주지 않아도 원하는 대로 정렬해주기 때문에 Comparator를 제거하였다.

다음으로는 정렬이 완료된 배열에서 붙어있는 원소끼리만 비교하면 나머지 원소들은 비교할 필요가 없다는 것을 깨달아서 이중 포문을 제거하고 붙어있는 원소들만 비교하도록 수정하였더니 효율성 테스트를 무사히 통과할 수 있었다.

추후 이와같은 탐색 알고리즘을 풀때 탐색되어져야 할 범위를 잘 확인 해야겠다.