[프로그래머스/자바] 전화번호 목록_42577

문제 및 코드

GitHub - Lee-Min-Jung/coding_test_practice

수정된 코드

GitHub - Lee-Min-Jung/coding_test_practice

생각

아래 처럼 생각해서 풀었는데 테스트 케이스는 통과하나 정답 통과는 되지 않는다... 효율성 통과가 되지 않는 것을 보니 이중 for문 때문에 시간복잡도가 n^2이어서 그런듯

// 생각
    // 짧은 전화번호가 긴 전화번호의 접두어가 될 수 있다
    // 전화번호 길이대로 정렬후 이중 for문
// 구현
    // 전화번호 길이 오름차순 정렬
    // phone_book 이중으로 돌면서 해당 전화번호가 뒤의 접두어로 존재하는지 확인

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        // 정렬
        Arrays.sort(phone_book, new Comparator<String>(){
            public int compare(String str1, String str2){
                return str1.length() - str2.length();
            }
        });
        
        // 이중 for문 돌기
        for(int i = 0; i<phone_book.length; i++){
            String target = phone_book[i];
            for(int j = i+1; j<phone_book.length; j++){
                if(phone_book[j].startsWith(target)){
                    return false;
                }
            }
        }
        
        return true;
    }
}

// 생각
    // phone_book을 사전순으로 정렬하면 다음 것이 본인으로 시작하는지만 for문 한 번에 확인하면 된다
// 구현
    // phone_book 사전 정렬(그냥 정렬하면 됨)
    // phone_book 돌기
        // 다음 것이 본인 것으로 시작하면 false 리턴
    // true 리턴

회고

• 문자열 길이 짧은 것 부터 비교해 나가면 접두 번호인지 확인할 수 있을 것 같다는 생각은 들었는데 문자 길이 기준 정렬하는 방법 몰라서 참고함. 
• 그런데 두번째 방법은 왜 되는 건지 아직 이해가 가지 않음...

----

• 솔직히 가장 먼저 생각난 건 글자 길이 순으로 정렬 후 이중 for문 도는 것이었다. 배열 제한 길이가 길어 시간 초과 날 것 같긴 했는데 다른 풀이가 번뜩 생각나지는 않는다.. 어김없이 시간 초과 및 실패.
• 다른 풀이를 참고 했다. 첫 번째 풀이로 사전순으로 정렬한 후 본인 다음 것이 본인으로 시작하는지 for문 한 번 돌면서 확인하는 코드가 있었다. 처음에는 이걸 하면 왜 for문 한 번만 도는거야? 라는 의문이 들었는데 곰곰이 생각해보니 사전순으로 정렬을 한다면 본인과 본인 뒤에 있는 모든 걸 다 확인할 필요가 없다. 사전순으로 정렬되니 본인 바로 뒤에 있는 것이 본인으로 시작하지 않으면 당연히 본인 뒤의 모든 것들은 본인으로 시작할 수가 없다. 그러니 이 방법을 사용하면 for문 한 번만 돌면서 답을 구할 수 있다.
• 그리고 다른 풀이는 HashMap을 사용하는 풀이가 있다. 어떻게 생각해내지? 싶긴 하나 막상 코드를 보면 어렵지는 않다... 처음에는 HashMap 코드도 이중 for문이니 n^2 아닌가 했는데 첫번째 for문은 전화번호 배열 길이만큼 돌고 두번째 for문은 최대 전화번호 길이만큼 도는데 전화번호 길이가 훨씬 짧아서 n^2까지는 안 가는 것 같다. 어쨋든 여기서 n은 배열 길이를 의미하니.
• 그리고 HashMap 코드에서 문자열 자체를 돌 때 맨 끝까지 확인하면 그 문자 자체가 map에 존재하게 된다. 그러니 맨 끝에서 하나 적은 곳까지만 확인을 해야 한다.

 

기억

• 정렬할 때 새로운 비교기준 주는 방법(문자열 배열 기준)

Arrays.sort(phone_book, new Comparator<String>(){
  public int compare(String str1, String str2){
  	return str1.length() - str2.length();
  }
 });

• 문자열 배열을 Arrays.sort(문자열 배열) 진행하면 사전순으로 정렬된다.

체크

풀이 횟수	시간	정답 여부	참고 여부
2	25분		O
3	1시간	X	O