[Java] Lv2 | 전화번호 목록

처음에는 ArrayList를 사용해서 풀었다. 

package week1.baek.hash;

import java.util.ArrayList;

public class Ex3 {
    public Boolean solution(String[] phone_book) {
        ArrayList<String> list = new ArrayList<>();

        for (String s : phone_book){
            list.add(s);
        }



        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.size(); j++) {
                if(i == j) continue;
                else if(list.get(i).startsWith(list.get(j))) return false;
            }
        }
        return true;
    }
}


class Ex3Main {
    public static void main(String[] args) {
        Ex3 ex3 = new Ex3();
        String[] phone_book = {"119", "97674223", "1195524421"};

        System.out.println(ex3.solution(phone_book));

    }
}

 

이렇게 하니까 정확도 테스트는 통과하는데 효율성 테스트에서 두 개가 안된다

 

1. 이중 for문 -> 단일 for문으로 개선

 

이중 for문으로 모든 원소들을 검색할 필요가 없었고, 주어진 배열을 정렬하고 검색하면 앞에 있는 원소가 뒷 원소의 접두사인지만 확인하면 됐다. 

 

ex) {"12", "123", "1236", "124"}

 

원래의 코드에서는 전체를 비교했지만, 이렇게 정렬을 하면 하나의 원소가 여러 개의 접두사여도 앞에 한개만 확인하면 바로 false를 반환하게 하면 된다. 

package week1.baek.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class Ex3 {
    public Boolean solution(String[] phone_book) {
        //오름차순 정렬
        Arrays.sort(phone_book);

        ArrayList<String> list = new ArrayList<>();

        for (String s : phone_book){
            list.add(s);
        }


        for (int i = 0; i < list.size()-1; i++) {
            if(list.get(i+1).startsWith(list.get(i))) return false;
        }
        return true;
    }
}




class Ex3Main {
    public static void main(String[] args) {
        Ex3 ex3 = new Ex3();
        String[] phone_book = {"119", "97674223", "1195524421"};

        System.out.println(ex3.solution(phone_book));

    }
}

 

 

1-1. 일반 배열에서도 startsWith를 사용할 수 있다. 

 

[최종 코드]

public class Ex3 {
    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;
    }
}

 

---

2. 해시 사용

 

---

[참고]

https://coding-grandpa.tistory.com/77

[프로그래머스] 전화번호 목록 (해시 Lv. 2) - 자바 Java

https://aroundlena.tistory.com/62