2. 전화번호 목록(프로그래머스, 해시 Level 2)

* 문제설명

 - 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
 - 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
    구조대 : 119
    박준영 : 97 674 223
    지영석 : 11 9552 4421

 - 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가

   다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

* 제한 사항
 - phone_book의 길이는 1 이상 1,000,000 이하입니다.
 - 각 전화번호의 길이는 1 이상 20 이하입니다.

 

역시나 제한사항에서 많은 생각을 하게 해 준 문제입니다.

문제로 나오는 테스트 케이스입니다.

순서	배열 값	나오는 결과 기대 값
1	{"123","456","789"}	참
2	{"12","123","1235","567","88"}	거짓
3	{"4321","432","122", "1334"}	거짓
4	{"119", "97674223", "1195524421"}	거짓

 

세번째를 제외하고 중복을 일으키는 값이 전부 뒤에 존재합니다.

다시 말해 앞, 뒤, 중간에 중복되는 값이 존재해서는 안된다는 것 입니다.

문제이름이 해쉬 이므로 여기서도 Map객체를 활용하였습니다.

    public static boolean solution2(String[] phone_book) {
        boolean answer = true;
        HashMap<String, String> checker = new HashMap<>();
        for(int j=0;j <phone_book.length  ;j++){
        	String arg = phone_book[j];
        	checker.put(arg, arg);  //대상을 넣습니다.
        }
        return answer;
    }	

 

단순하게 맵객체에 데이터를 넣는 모습입니다.

데이터를 넣어준 다음에 키값을 대상으로 맵객체에 값이 존재하는지에 대해서 반복문을 동작하게 하였습니다.

    public static boolean solution2(String[] phone_book) {
        boolean answer = true;
        HashMap<String, String> checker = new HashMap<>();
        for(int j=0;j <phone_book.length  ;j++){
        	String arg = phone_book[j];
        	checker.put(arg, arg);  //대상을 넣습니다.
        	for(int i=0;i < arg.length();i++){ //본인의 키 값 패턴이 다른곳에도 있는지 
        		String mini = arg.substring(0,i);  //하나하나 늘려가며
        		if(checker.get(mini) != null){  //조사합니다.
        			answer = false;
        			break;
        		}
        	}            
        }
        return answer;
    }	

 

여기까지 하고나면 사실 거의다 끝난 것이라 볼 수 있습니다.

자신의 전화번호값에서 substring을 통해서 자기 이외의 패턴이 존재하는지 조사를 하게 하였습니다.

그런데 이렇게 하고나면 문제가 되는 케이스가 1개 존재합니다.

바로 위에서 언급한 3번째 경우 입니다.

4321 이라는 값은 뒤에 432가 존재하기 때문에 거짓이 나와야 하지만, 위의 반복문 에서는 이미 4321이 조사를 끝낸 상황 이므로 432에 대해서 찾지를 못하게 되어 결과가 참(true)이 나오게 됩니다.

 

그러므로 위 코드에서 필요한 것이 바로 배열의 "정렬" 입니다.

간단하게 정렬만 추가하여 보겠습니다.

    public static boolean solution2(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);  //정렬합니다.
        HashMap<String, String> checker = new HashMap<>();
        for(int j=0;j <phone_book.length  ;j++){
        	String arg = phone_book[j];
        	checker.put(arg, arg);  //대상을 넣습니다.
        	for(int i=0;i < arg.length();i++){ //본인의 키 값 패턴이 다른곳에도 있는지 
        		String mini = arg.substring(0,i);  //하나하나 늘려가며
        		if(checker.get(mini) != null){  //조사합니다.
        			answer = false;
        			break;
        		}
        	}            
        }
        return answer;
    }	

 

이렇게 정렬을 하게 되면 4321보다 432가 먼저 앞에 놓이게 되므로 반복문을 통한 검사에서 걸리게 되는 것 입니다.

위의 내용을 한번 채점하여보겠습니다.

짜잔~ 통과하였습니다.

 

Map 객체를 통해서 간단하게 구현하여 보았습니다.

반복문을 사용하면 효율성에서 문제가 되어 걸릴줄 알았지만...

채점 후 다른 분들의 코드 중 반복문을 통해서 구현하신 내용을 보고 감탄하였습니다..

이러한 실력들은 어디서 나오는지..ㅠ

열심히 노력 해야겠습니다!