Programmers 전화번호 목록: Hash

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

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

HashMap을 사용하고 싶은데.. 처음에 key와 value를 어느 값으로 잡아야하는지 감이 오지 않았다.

고민하다 내가 생각한 방법은 key는 String으로 value는 Integer로 잡아 value로 오름차순을 해서 iterator로 비교하면서String값을 subString으로 비교해서 같은게 있으면 false로 반환하는 거였다.

 

HashMap 정렬 방법을 구글링하다가 Collentions.sort()으로 정렬이 된다고 해서 알아봤는데 안됨

//value값으로 정렬 오름차순!!
List<String> list = new ArrayList<String>();
Collections.sort(list, (o1, o2) -> (map.get(o2).compareTo(map.get(o1)))); //오름차순은 map.get의 o1, o2 자리 바꿔주기
System.out.println(list.size());

for문 돌면서 <String, Integer>로 HashMap인 map에 넣어줘도 list.size()값이 0으로 떴다. 

 

한참 뻘짓하다가 다시 참고한 코드를 확인해보니 List를 선언해줄때 new ArrayList<String>(map.keySet());을 해줘야 했다 ㅠㅠ list에 key값이 있어야 o1, o2의 value값들을 확인할텐데.. 허허 

 

이렇게 정렬해놓고 string의 substring들을 비교해준 코드

public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < phone_book.length; i++) {
        	if(map.containsKey(phone_book[i])) return false;
        	map.put(phone_book[i], Integer.parseInt(phone_book[i]));
		}
        
        //value값으로 정렬 오름차순!!
		List<String> list = new ArrayList<String>(map.keySet());
        Collections.sort(list, (o1, o2) -> (map.get(o1).compareTo(map.get(o2)))); //오름차순은 map.get의 o1, o2 자리 바꿔주기
        System.out.println(phone_book.length+" "+map.size()+" "+list.size());
        for (int i = 0; i < list.size(); i++) {
			for (int j = i+1; j < list.size(); j++) {
                System.out.println(list.get(i)+" "+list.get(j));
				if(list.get(i).substring(0).equals(list.get(j).substring(0, list.get(i).length()))) {
					answer = false;
					break;
				}
			}
		}
        
        return answer;
    }

 는 당연히 효율성 0... 테케는 다 맞았지만 효율성 체크에서 다 fail 뜸ㅠㅠ sort api 쓰고.. 이중for문까지 도는디 시간 초과가 안날 수가 없다.

 

결국 못풀어서 인터넷 검색했는데 해쉬로 푼 사람이 하나도 없다. 제일 좋은 풀이는 indexOf() 나 .startsWith()로 푼 풀이었다. 사실 startsWith는 처음 알았당 ..ㅋㅋㅋ 알고리즘은 진짜 많이 풀어봐야 한다는걸 다시 한 번 느꼈다. 근디 이 문제는 왜 해쉬 카테고리에 있는거쥐... 왜쥐... 나중에 다시 도전해보겠음

 

문자열.indexOf(String str) : 문자열안에 str이 있는 경우 시작 인덱스를 반환, 없는 경우는 -1 반환 (return Integer)

Returns the index within this string of the first occurrence of the specified substring.

The returned index is the smallest value k for which:

this.startsWith(str, k)

If no such value of k exists, then -1 is returned.Parameters:str the substring to search for.Returns: the index of the first occurrence of the specified substring, or -1 if there is no such occurrence.

 

문자열.startsWith(String prefix) : 문자열이 prefix로 시작하면 true 반환, 아니면 false 반환 (return boolean)

Tests if this string starts with the specified prefix.Parameters:prefix the prefix.Returns:true if the character sequence represented by the argument is a prefix of the character sequence represented by this string; false otherwise. Note also that true will be returned if the argument is an empty string or is equal to this String object as determined by the equals(Object) method.

---

//indexOf()
	public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        for (int i = 0; i < phone_book.length; i++) {
			for (int j = i+1; j <= phone_book.length; j++) {
				if(phone_book[j].indexOf(phone_book[i]) == 0) return false;
			}
		}
        return answer;
    }

//startsWith()
    public boolean solution(String[] phoneBook) {
       for(int i=0; i<phoneBook.length-1; i++) {
            for(int j=i+1; j<phoneBook.length; j++) {
                if(phoneBook[i].startsWith(phoneBook[j])) {return false;}
                if(phoneBook[j].startsWith(phoneBook[i])) {return false;}
            }
        }
        return true;
    }