[Programmers] 고득점 Kit - Hash : 전화번호 목록 #42577

문제 링크

전화번호 목록

문제 조건

• 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인해야 한다.
• phone_book의 길이는 1 이상 1,000,000 이하이다.
• 각 전화번호의 길이는 1 이상 20 이하이다.
• 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 한다.

변수 설명

• 매개변수
  • phone_book : 전화번호들이 담긴 배열
• len : phone_book 배열의 길이

코드 설명

1. 이중 for문을 통해 phone_book 안에 있는 요소들을 비교해줘야 한다.
2. 이 때, startsWith 메서드를 사용하여 phoen_book[i]가 phone_book[j]의 접두어인지 검사해야 한다.
3. 물론 phone_book[j]가 phone_book[i]의 접두어인지도 검사해준다.

다른 방법

• 이중 for문이 아닌 다른 방법으로 생각해보았다.
• phone_book을 정렬해줌으로써 O(n)으로 해결하였다.
  • 정렬해주면 접두어로 쓰이는 string은 무조건 맨 앞에 있으므로 검사에 유리하다.

다른 코드

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

배운 점

• startsWith라는 메서드를 처음 알게 되었다.
  • 접두문자를 사용하는지 확인해주는 String 메서드이다.

문제 해답

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        int len = phone_book.length;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(phone_book[i].startsWith(phone_book[j])) return false;
                if(phone_book[j].startsWith(phone_book[i])) return false;
            }
        }
        return answer;
    }
}
public class Main {
    public static void main(String[] args) {
        Solution Test = new Solution();
        String[] p = {"119", "97674223", "1195524421"};
        boolean answer = Test.solution(p);
        System.out.println(answer);
    }
}