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

🔗 문제 링크

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

👨🏻‍💻 처음 작성한 코드

※ 효율성 테스트3,4번 런타임 에러 발생

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        for(int i=0; i< phone_book.length; i++){
            for (int j=0; j< phone_book.length; j++) {
                if (i == j) continue;
                if (phone_book[i].length() < phone_book[j].length()){
                    if (phone_book[i].equals(phone_book[j].substring(0, phone_book[i].length()))) 
                        return false;
                }
                
            }
        }
        
        return answer;
    }
}

📌 문자열의 시작을 phone[i]로 시작하는지 체크하기 위해 초기 코드에 다음과 같은 조건문을 추가했다.

if (phone_book[i].equals(phone_book[j].substring(0, phone_book[i].length())))

위의 코드는 equals(), substring()메서드를 활용하여 표현하였는데 startsWith()메서드를 사용해 쉽게 표현 가능하다.

if (phone_book[j].startsWith(phone_book[i]))

📌 startsWith(), endsWith()를 기억해두자!!
📌 start, end뒤에 s가 들어가는 것도 주의.

👨🏻‍💻 최종 코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Arrays.sort(phone_book);

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

📝 결론

처음 코드의 경우 2중 for문을 통해 모든 문자열에 대해서 다른 모든 문자열들과 비교를 하는식으로 코드를 작성하였다. 그래서 첫 코드의 시간복잡도는 $O(n^2)$이어서 코드의 logic은 맞음에도 불구하고 효율성테스트 3,4번에서 런타임 에러가 발생하였었다.

어떻게 코드를 변경하면 코드의 효율성을 높일 수 있을까? 하는 생각을 하며 HashSet을 활용하여 코드를 변경해복도 하였으나 잘 실행되던 문제들에서도 런타임에러가 발행하며 효율이 더 안좋아지는 상황이 발생하기도 하였다. 그리하여 $O(n^2)$의 시간복잡도를 $O(n)$ 으로 줄여야겠다는 다짐을 하고 다시 생각을 하였다.

그 결과 위의 최종 코드와 같이 Array를 sort하여 정렬을 하고 모든 경우의 수가 아닌 각각의 문자열에 대해서 다음 문자열과 비교를 하도록 코드를 변경하며 for문을 하나만 사용하여 시간복잡도를 $O(n)$으로 줄였다.

※ 해당 문제의 경우는 접두사가 해당하는 수를 count하는 것이 아닌 존재 유무만을 나타내는 것이기에 모든 경우의 수를 탐색할 필요가 없기에 for문 하나로 각각의 다음 문자열과 비교를 하여 연산을 줄일 수 있었다.

Arrays.sort()로 String배열을 sort할 경우 앞 자리부터 비교를 하기에 ["119", "97674223", "1195524421"]의 경우 ["119", "1195524421", "97674223"]와 같이 정렬이 되며 ["banana", "apple", "ant"]의 경우 ["ant", "apple", "banana"]과 같이 정렬이 된다.