[코테연습] 전화번호목록

프로그래머스 문제 중, 동일한 접두어가 있는 경우 TRUE, 아닐 경우 FALSE 를 반환하는 문제를 풀었다.

 

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

프로그래머스

 

내가 처음 시도 한 코드는 다음과 같다

 

public boolean solution(String[] phone_book) {

        boolean answer = true;

 

        Queue<String> queue = new LinkedList<>();

        queue.offer(phone_book[0]);

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

            if (!answer) break;

            System.out.println("queue : "+queue);

            String phone = phone_book[i];

            Queue<String> savePhone = new LinkedList<>();

            while (!queue.isEmpty()) {

                String prevPhone = queue.poll();

                System.out.println("prevPHone : "+prevPhone+", phone : "+phone+"// "+phone.startsWith(prevPhone));

                if (phone.startsWith(prevPhone)) {

                    answer = false;

                    break;

                }

                savePhone.offer(prevPhone);

            }

            savePhone.offer(phone);

            queue = new LinkedList<>(savePhone);

        }

        System.out.println("answer : "+answer);

        return answer;

    }

 

 

해당 방법을 했을 때, phone_book 에 해당하는 배열을 Queue 에 저장해둔 리스트와 하나씩 다시 검사하는 방법을 취했다.

즉, 

 

phone_book 배열의 다음 요소와 Queue 의 요소가 일치하지 않는다면, Queue에 다시 저장해서 처음부터 검사하는 것이다.

log 로 찍으면 다음과 같다.

 

queue : [123]
prevPHone : 123, phone : 456// false
queue : [123, 456]
prevPHone : 123, phone : 789// false
prevPHone : 456, phone : 789// false
answer : true //break;

 

이렇게 코드를 짰을 경우에는 아쉽게도 정답은 맞았지만 효율성에서 시간초과가 발생했다.

 

 

public boolean solution(String[] phone_book) {

        boolean answer = true;

        Arrays.sort(phone_book);

       

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

            String nowPhone = phone_book[i];

            String nextPhone = phone_book[i+1];

            if (nextPhone.startsWith(nowPhone)) {

                answer = false;

                break;

            }

        }

        System.out.println("answer : "+answer);

        return answer;

    }

 

 

수정한 코드는 다음과 같다. 조금 더 단순하게 생각해서, phone_book 배열을 Arrays.sort 로 오름차순 정렬한 뒤에,

앞 뒤의 String 값을 비교하는 것이다.

 

이 경우에는 시간복잡도가 최대 O(n) 만 발생하여 효율성 검사도 무사히 통과 가능했다.