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

1. 문제

---

• 제한 사항
  • phone_book의 길이는 1 이상 1,000,000 이하입니다.
    • 각 전화번호의 길이는 1 이상 20 이하입니다.
    • 같은 전화번호가 중복해서 들어있지 않습니다.
• 입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

• 입출력 예 설명
  • 입출력 예 #1
    앞에서 설명한 예와 같습니다.
  • 입출력 예 #2
    한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
  • 입출력 예 #3
    첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

 

2. 초기 아이디어

---

• 기준 하나를 잡고 해당 String이 다른 String의 접두어인지 확인.
  • 첫 번째 문자열(current)의 length 를 확인 
  • 나머지 문자열을 length만큼 자름(head)
  • current와 head가 같은지 확인.
  • 다음 문자열로 이동.
  • 반복
• 주의사항
  • length 크기순으로 정렬이 안되어 있을 수 있음.
    • 추가) 정렬이 안돼있으면 정렬을 하자 ㅋㅋㅋㅋㅋㅋㅋ
    • Arrays.sort()이용.

 

 

3. 코드

---

public boolean solution(String[] phone_book) {
    boolean answer = true;

    for (int i = 0; i < phone_book.length-1; i++){
       String current = phone_book[i];

       for (int j=0; j < phone_book.length; j++){
           if (i!=j && phone_book[j].length() >= current.length()){
               String head = phone_book[j].substring(0, current.length());

               if (head.equals(current)){
                   return false;
               }
           }

       }
    }
    return answer;
}

 

4. 결과

---

• 효율성이 떨어진다..흠..

 

 

 

5. 코드 개선 - stream.filter()

---

• 흠... 일단 코드를 줄여보자.
• 이번엔 stream.filter()를 사용했다.
• 코드는 간결해 졌을지 몰라도, 시간복잡도는 O(n^2)로 그대로이다.
  • 결국 startWith() 안에서 반복문이 돌기 때문..
• result.size() >1 : 전부다 확인하기 때문에 본인도 포함됨.

public boolean solution(String[] phone_book) {
    boolean answer = true;

    for (int i = 0; i < phone_book.length-1; i++){
       String current = phone_book[i];
       List<String> result = Arrays.stream(phone_book).filter(n -> n.startsWith(current)).collect(Collectors.toList());
        if (result.size() > 1){
            return false;
        }

    }
    return answer;
}

 

 

 

6. 코드 개선 : 정렬

---

• 코드를 더 줄여보자.
• 먼저 정렬이 안돼있으니 정렬부터 하자ㅋㅋㅋㅋㅋㅋㅋㅋ
• 그러면 길이 순서대로 정렬이 된다.
• 즉 다음 문자열의 접두어에 이전 문자열이 포함되는지 확인하면 된다.

public boolean solution(String[] phone_book) {
    boolean answer = true;

    Arrays.sort(phone_book);

    for (int i = 0; i < phone_book.length-1; i++){
       String current = phone_book[i];

        if (phone_book[i+1].startsWith(current)){
            return false;
        }

    }
    return answer;
}

 

 

 

 

7. 코드개선 : 해시

---

• 근데 이 문제는 "해시" 문제이다..
• 어떻게 적용하지?
  • containsKey(), contatinsValue()를 활용할 때 장점이 있다.
• 전화번호를 hash에 넣어둔다.
• 현재 전화번호의 접두어 부분을 루프를 돌며서 하자리씩 늘려나간다.
• 해당 접두어가 다른 번호와 일치하는지 확인
  • 즉 어떤 번호가 다른 번호의 접두어인지 확인이 가능함.

public boolean solution(String[] phone_book) {
    boolean answer = true;
    HashMap<String, Integer> map = new HashMap<>();

    for (String number : phone_book) {
        map.put(number, 0);
    }

    for (int i=0; i < phone_book.length; i++){
        for (int j=0; j<phone_book[i].length();j++){
            if (map.containsKey(phone_book[i].substring(0, j))){
                return false;
            }
        }

    }

    return answer;
}

 

 

8. GitHub : 211125 PhoneBook

---

GitHub - bsh6463/coding_test