[Programmers Level 2] 전화번호 목록

문제

프로그래머스

 

첫번째 시도

해시를 사용할 방법이 떠오르지 않아서 일단 배열의 반복문을 사용해서 시도해봤다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        /*
            1. 길이 순으로 정렬
            2. 가장 짧은 길이의 번호를 기준으로 각 문자열의 substring을 비교
            3. 루프를 한번 돌고, 다음 인덱스로 넘어가서 반복
        */
        
        // 문자열 길이 순으로 정렬, 짧은 문자열이 긴 문자열로 시작하는 경우는 없음
        Arrays.sort(phone_book, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        });
        
        // 가장 짧은 길이의 번호를 기준으로 각 문자열의 substring을 비교
        for (int i = 0 ; i < phone_book.length-1 ; i ++) {
            
            // 현재 인덱스에 있는 문자열 저장
            String s = phone_book[i];
            
            for (int j = i+1 ; j < phone_book.length ; j ++) {
                
                // 접두어가 있으면 바로 false 반환
                if (phone_book[j].startsWith(s)) {
                    return false;
                }
            }
        }
        
        // for문 다 돌고나서도 접두어가 없으면 true 반환
        return true;
        
        
    }
}

 

결과

효율성 테스트 4개 중 2개 빼고 통과..!

3, 4번에서 계속 시간초과 뜬다ㅡ.ㅡ

 

힌트를 찾아본 결과 for문을 한번만 쓰고, 비교도 바로 뒤 문자열과만 비교하면 된다고 한다고 해서 다시 시도!

 

---

 

두번째 시도

힌트 참고해서 다시 풀었음! 이중 for문을 쓰던걸 하나로 줄여서 시간 복잡도가 O(n^2)에서 O(n)으로 줄었따 👏🏻

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        /*
            1. 문자열 배열 정렬 (문자열 > 길이 순으로 정렬)
            2. 뒤의 문자열이 앞의 문자열로 시작하면 바로 false 반환
            3. 루프를 한번 돌고, 다음 인덱스로 넘어가서 반복
        */
        
        // 문자열 배열 정렬
        Arrays.sort(phone_book);
        
        // System.out.println(Arrays.toString(phone_book));
        
        // 가장 짧은 길이의 번호를 기준으로 각 문자열의 substring을 비교
        for (int i = 0 ; i < phone_book.length-1 ; i ++) {
            
            // 현재 인덱스에 있는 문자열 저장
            String s = phone_book[i];
            
            if (phone_book[i+1].startsWith(phone_book[i])){
                return false;
            }
        }
        
        return true;
        
    }
}

 

문자열 배열을 정렬을 이해하면 쉽게 풀 수 있다.

정렬 시 문자열 > 문자열 길이 순으로 정렬되기 때문에 만약 앞의 문자열을 포함하는 문자열이 있으면, 해당 문자열 바로 뒤에 위치하게 된다!

 

 

결과