== 전화번호 목록 ==

한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 함

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

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 
그렇지 않으면 true를 return 하도록 solution 함수를 작성
Markdown
복사

•

문제 이해는 어렵지 않은데 접근법에 대해서 고민을 했던 문제였다.

•

substring을 활용하여 접두어를 찾아서 문제를 해결하는 방향으로 접근하려고 했지만 실패했다.

•

HashMap으로 풀이한 것 이외에 다른 방법으로도 접근해봤다.

◦

startsWith을 활용하여 접두어만 추출해서 비교하는 방식으로 접근했으나 효율성 테스트에서 시간 초과가 발생하였다.

◦

정렬을 활용하여 해결하려고 했으나 정확성 테스트에서 실패하였다(효율성 테스트는 성공).

해결 방법

•

substring과 HashMap을 활용해야 한다. 배열 요소들을 HashMap에 추가한 다음에 HashMap에 있는 키를 substring을 활용하여 포함 여부를 확인하는 방식으로 접근해야 한다.

코드

•

자료구조를 사용하지 않음 (실패)

public class Pro42577 {
    public boolean solution(String[] phone_book) {
        int length = phone_book[0].length();

        int pLength = phone_book.length;
        for (int i = 1; i < pLength; i++) {
            if (phone_book[i].substring(0, length).equals(phone_book[0])) {
                return false;
            }
        }
        return true;
    }
}
Java
복사

•

HashMap 활용

import java.util.HashMap;

public class Pro42577 {
    public boolean solution(String[] phone_book) {
        int length = phone_book.length;
        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < length; i++) {
            map.put(phone_book[i], i);
        }

        for (String s : phone_book) {
            length = s.length();
            for (int j = 0; j < length; j++) {
                if (map.containsKey(s.substring(0, j))) {
                    return false;
                }
            }
        }

        return true;
    }
}
Java
복사

•

startsWith 활용 - 효율성 테스트에서 시간 초과 발생

public class Pro42577 {
    public boolean solution(String[] phone_book) {
        int length = phone_book.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (phone_book[i].startsWith(phone_book[j])) {
                    return false;
                }

                if (phone_book[j].startsWith(phone_book[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}
Java
복사

•

정렬을 활용한 풀이 - 효율성 테스트 성공, 정확성 테스트 실패

import java.util.Arrays;

public class Pro42577 {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        boolean result = true;

        int length = phone_book.length;
        for (int i = 0; i < length - 1; i++) {
            if (phone_book[i + 1].contains(phone_book[i])) {
                result = false;
                break;
            }
        }
        return result;
    }
}
Java
복사

느낀 점

•

substring, HashMap, 정렬, startsWith의 활용법에 대한 내용을 알 수 있었다.

•

접두어가 아닌 접미어를 구하는 경우에도 이와 유사한 로직을 활용하여 접근하면 해결할 수 있을 것이라는 생각이 들었다.