[JAVA] Lv.2 전화번호 목록 - 프로그래머스

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

프로그래머스

# 처음 오답 코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() < o2.length()) return -1;
                else if (o1.length() > o2.length()) return 1;
                return 0;
            }
        });
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = i + 1; j < phone_book.length; j++) {
                if(phone_book[j].startsWith(phone_book[i]))
                    return false;
            }
        }
        return answer;
    }
}

- 효율성 3, 4 통과 X : 이중 for문이 원인 / for문 1번만 사용해 풀 수 있는 방법?

 

- 처음에 이중 for문 사용 : 효율성 3, 4 통과 못함

 

"123", "12345", "1245", "1243", "12"  을 정렬하면 12, 123, 12345, 1243, 1245 로 정렬됨

즉, 접두어 번호가 있으면 정렬하면서 필연적으로 붙어나올 수 밖에 없음

정렬한 후, for문 돌면서 number[i+1].startWith(number[i])인지 체크
  * i가 i+1의 접두어인 경우 무조건 i+1보다 먼저 나오므로(길이가 짧거나 같으니) 유효함

 

 

# 정답 코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        
        Arrays.sort(phone_book);
        for(int i=0; i < phone_book.length-1; i++){
            if(phone_book[i+1].startsWith(phone_book[i])) 
                return false;
        }
        return true;
    }
}