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

 

풀이 : 이문제를 읽자마자 찾아본건 접두어이다...

       " 접두사는 어떤 단어의 앞에 붙어 뜻을 첨가하여 하나의 다른 단어를 이루는 말 " 이라고 해서 Contains 는 제외

        1. hash 문제이니 만큼 hashmap 을 사용한다 인자는 String, List<String> 

        2. HashMap 을 채울때 Key 값을 넣고 List 는 Key 값을 제외한 값으로 List 로 변환하여 넣는다.

        3. Key 별로 List 를 Foreach로 돌려 접두어 인지 체크하여 하나라도 false 시 Break 진행

           접두어 확인 방법 : IndexOf, StartWith 등등...

       하지만 효율성이 0점...

package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.logging.Logger;

public class PhoneNumberBookList {

    static String[] phone_book = {"12","123","1235","567","88"};
    private final static Logger LOG = Logger.getGlobal();

    public static void main(String[] args) {
        System.out.println(solution(phone_book));
    }
    public static boolean solution(String[] phone_book) {
        boolean answer = true;

        HashMap<String, List<String>> _hashmap = new HashMap<>();
        ArrayList<String> _list;

        for (int i = 0; i < phone_book.length; i++)
        {
            _list = new ArrayList<>(Arrays.asList(phone_book));
            _list.remove(i);
            _hashmap.put(phone_book[i], _list);
        }

        for (String _key: _hashmap.keySet())
        {
            for (String value :_hashmap.get(_key))
            {
                if (_key.length() > value.length()) continue;
                if (value.indexOf(_key) == 0)
                {
                    answer = false;
                    break;
                }
            }
            if(answer == false) break;
        }

        return answer;
    }
}

Key 값을 제외한 List 를 만들어서 무리하게 진행 하니 데이터가 커질수록 시간이 배로 든다... n + n^2 쯤...

그래서 친구에게 물어보니 List 를 String 으로 하고 뒷부분 접두어 확인 부분의 조건을 바꾸어 통과 하게되었다..

이래서는.. Key 값을 제외한 배열을 안쓰게 되어서 굳이 할필요가 없지만 List 변환은 시간이 걸린다는걸 알게되었다.

package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.logging.Logger;

public class PhoneNumberBookList {

    static String[] phone_book = {"12","123","1235","567","88"};
    private final static Logger LOG = Logger.getGlobal();

    public static void main(String[] args) {
        System.out.println(solution(phone_book));
    }
    public static boolean solution(String[] phone_book) {
        boolean answer = true;

        HashMap<String, String[]> _hashmap = new HashMap<>();

        for (int i = 0; i < phone_book.length; i++)
            _hashmap.put(phone_book[i], phone_book);

        for (String _key: _hashmap.keySet())
        {
            for (String value :_hashmap.get(_key))
            {
                if (_key.length() >= value.length() ) {
                    continue;
                }
                else
                {
                    if (value.indexOf(_key) == 0)
                        return false;
                }


            }
            if(answer == false) break;
        }

        return answer;
    }
}

이거말고 어떻게 해쉬를 사용하여 푸는지 알아보고 싶어 찾게 된것이 Trie 자료구조라는것이 있었다.

해당 내용 공부를 해야할것 같다...