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

문제 이해 및 제한 사항

프로그래머스의 해시 문제, 전화번호 목록 LV2

https://programmers.co.kr/learn/courses/30/lessons/42577

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

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

매개변수로 주어지는 전화번호 목록에서 어떤 번호가 다른 번호의 접두사인 경우가 1개라도 있으면 false를, 그렇지 않다면 true를 반환하는 문제입니다.

 

 

 

문제 해결 순서

1. 해쉬의 KEY와 VALUE에 어떤 값을 넣어서 문제를 해결할지 고민한다.   

• 배열을 순회하면서 key에는 번호를, value에는 int형 타입을 넣는다. 아무리 생각해봐도 value를 쓸 일이 없을 것 같다.

2.  접두어가 있는지 체크하는 로직을 생각한다.

• 각 배열을 순회하고, 각 인덱스에서 번호의 길이만큼 순회하면서 해당 번호의 접두어가 map에 있는지 체크한다. (길이보다 1개 작은만큼 순회하도록 해서 접두어를 체크한다. 전체 단어길이만큼 순회하면 자기 자신이 포함되므로)
• 접두어가 map에 포함되어있으면 false를 리턴한다.

 

코드

이전통과되기 까지 여러 소스코드를 작성해보았는데, 효율성 테스트에서 모두 걸렸습니다. 아래 코드는 참고만 하면 좋을 듯 합니다.

1번째 코드

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

        // 해쉬에 전화번호와 접두사 횟수 담기(자기 자신 포함해서 1)
        for (String phone : phone_book) {
            map.put(phone, 0);
        }

        for (String prefixPhone : map.keySet()) {
            // 반복문 돌면서 prefixPhone이 접두사로 있으면 -1하기
            for (String phone : map.keySet()) {
                if (phone.equals(prefixPhone))
                    continue;
                if (phone.startsWith(prefixPhone)) {
                    answer = false;
                    break;
                }
            }
            if (answer == false)
                break;
        }

        return answer;
}

 

2번째 코드

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

        Arrays.sort(phone_book);
        // 해쉬에 전화번호와 접두사 횟수 담기(자기 자신 포함해서 1)
        for (String phone : phone_book) {
            map.put(phone, 1);
        }

        for (String prefixPhone : map.keySet()) {
            // 반복문 돌면서 prefixPhone이 접두사로 있으면 -1하기
            for (String phone : map.keySet()) {
                if (phone.startsWith(prefixPhone)) {
                    map.put(prefixPhone, map.get(prefixPhone) - 1);   // 접두사이면 접두사인 key의 value에 -1
                }
            }
            // min보다 작으면 min으로 저장
            if (map.get(prefixPhone) < min)
                min = map.get(prefixPhone);
        }

        //  0 미만인 value가 있으면 false 리턴
        if (min < 0) answer = false;

        return answer;
}

 

결과

 

 

통과한 코드입니다.

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

        // 해쉬에 전화번호와 접두사 횟수 담기(value에 무엇을 담든 상관없다.)
        for (int i = 0; i < phone_book.length; i++) {
            map.put(phone_book[i], i);
        }

        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 1; j < phone_book[i].length(); j++) {      // 끝에서 두번째까지만 탐색해서 그 값이 있으면 접두어가 있는 것으로 처리 (끝까지 탐색하면  자기 자신)
                System.out.println("phoneBook은 "+ phone_book[i]);
                System.out.println(phone_book[i].substring(0, j));
                if (map.containsKey(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }
        return true;
}

 

 

결과

 

 

 

 

 

참고글 : 자세한 설명이 나와있어 좋은 글입니다. 
위 코드의 깃허브 코드

GitHub - BananMoon/algorithm_study