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

프로그래머스

해시로 분류되어있는 문제이나, 시간복잡도를 줄여 단순비교를 하는 방식으로 풀었다.

 

- 처음에는 단순하게 반복문을 두 번 돌며 접두어 포함여부를 확인하였으나 효율성테스트에서 걸림(n^2)

- 사전순으로 정렬 후, 한 바퀴만 돌면서 인접 문자열의 접두어 포함여부만 비교하니 효율성 테스트를 통과함 (n)

 

Note

- contains() 메서드를 사용할 경우 문자열 중간에 포함되는 경우를 거를 수가 없어 몇몇 테스트 케이스에서 걸린다.

- 정답코드에서 input명이 쓸데없이 길어 phone_book -> contact로 변경했다.

import java.util.*;

class Solution {
    public boolean solution(String[] contact) {

        Arrays.sort(contact);
        
        for(int i = 0; i < contact.length - 1; i++){
            
            String curr = contact[i];
            String next = contact[i + 1];
            
            int minLen = curr.length() < next.length() ? curr.length() : next.length();
            
            if(curr.substring(0, minLen).equals(next.substring(0, minLen))){
                return false;
            }
                
        }
        
        return true;
    }
}​