[Java] 프로그래머스 Lv.2 > 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577?language=java 

코딩테스트 연습 - 전화번호 목록

 

풀이

해시문제인데 아직 해시를 잘 모르겠어서 일단.. 마음대로 풀었다^^..

처음에는 for문을 2번 돌려서 비교했는데, 효율성 테스트에서 실패가 떴다.

=> 배열을 먼저 sort(정렬)해주고, for문을 한번만 돌리도록 수정했다.
( ["119", "1195524421", "97674223"]와 같이 사전순으로 정렬되니, 앞 뒤로만 비교해주면 됨)

import java.util.Arrays;
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        // string 배열 두개씩 비교
        String a="",b="";
        for(int i=0; i<phone_book.length-1; i++){
                a = phone_book[i];
                b = phone_book[i+1];
                //System.out.println("a:"+a+"b:"+b);

                // 더 짧은 쪽의 길이만큼 처음부터 비교
                // 접두어 있으면 false 없으면 true return
                int min = Math.min(a.length(),b.length());
                for(int k=0;k<min;k++){
                    // System.out.println("ak:"+a.charAt(k)+"bk:"+b.charAt(k));
                    if(a.charAt(k)!=b.charAt(k)) break;
                    else if(k==min-1) return false; 
                }
        }
        return true;
    }
}

 

HashMap 사용

전화번호와 해당 배열순서를 hashmap의 key와 value값으로 put 해준다.

Map.containsKey(key)

HashMap에 특정 key 존재 여부 확인하는 메소드.
Map에서 인자로 보낸 key가 있으면 true 없으면 false를 반환한다.

첫번째 전화번호의 앞에서부터 하나씩 잘라서 map에 같은 번호가 들어있는지 비교해서 접두어인 경우가 있는지 확인한다. 같은게 있다면 최종적으로 false를 리턴해준다.

ex) 예를들어 전화번호부에 ["12345", "12"] 가 들어 있다면 "12345"를 "12"까지 잘라 containsKey함수의 인자에 넣어주엇을때 true를 리턴하게 된다. 따라서 answer=false...

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phoneBook) {
        boolean answer = true;
            Map<String, Integer> map = new HashMap<>();
            for(int i = 0; i < phoneBook.length; i++) {
                map.put(phoneBook[i], i);
            }

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