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

문제 :

 

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

 

풀이 1 : 테스트 15 실패 :

import java.util.HashSet;
import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        //접두사를 찾는 것이므로 정렬하면 쉽게 비교 가능
        Arrays.sort(phone_book);
        
        HashSet<String> hs = new HashSet<>();
        //첫번째 수는 무조건 넣어주고
        hs.add(phone_book[0]);
        //뒤에 오는 숫자를 앞에오는 숫자 길이만큼 잘라서 해시에 저장
        //뒤에오는 숫자 길이가 더 짧을 경우 그대로 저장
        for (int i=1; i<phone_book.length; i++) {
        	if(phone_book[i].length() <= phone_book[i-1].length()) {
        		hs.add(phone_book[i]);
        	} else {
        		hs.add(phone_book[i].substring(0,phone_book[i-1].length()));        		
        	}
        }
        //해시에 저장된 수의 갯수가 phone_book보다 적다면 중복이 있단 말이므로 false 리턴
        if(phone_book.length > hs.size()) answer = false;
        return answer;
    }
}

-> 이렇게 푸니까 테스트 15번만 틀리고 효율성 테스트까지 다 통과했다...

한 30분 고민해봤는데 도저히 어딜 고쳐야할지 모르겠어서 ㅠㅠ

HashSet 말고 HashMap써서 다시 풀어보았다!

 

풀이 2 : 정답 :

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        //벨류값은 필요 없지만 containsKey 메소드 이용을 위해 해시맵 사용
        HashMap<String, String> hashMap = new HashMap<String, String>();

        for (int i = 0; i < phone_book.length; i++) {
            hashMap.put(phone_book[i], " ");
        }

        for (String p : phone_book) {
            for (int i = 0; i < p.length(); i++) {
                if (hashMap.containsKey(p.substring(0, i))) {
                    answer = false;
                }
            }
        }
        return answer;
    }
}

-> HashMap을 쓴 가장 큰 이유! containKey를 쓰기 위해서! :)

그 결과 테스트 15까지 다 통과했다!

효율성 테스트 부분에서는 위의 1번 코드랑 비슷비슷하게 나왔다!

1번 코드에서 틀린 부분 아시는 분 알려주세요 ㅠㅠㅋ

 

풀이 3 : 테스트 케이스 추가 전 모범답안 : 

class Solution {
    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;
    }
}

-> 해당 문제가 21년 3월 테스트 케이스가 추가되었다고 나와있는데,

그 전 기준으로 가장 많은 좋아요를 받은 & 정답인 코드이다!

대신 현재는 이 코드로 제출할 경우 효율성테스트 3, 4번을 통과하지 못한다고 하니

역시 이중for문은 효율성 측면에서 지양해야할 것 같다!

하지만 startWith이라는 것을 처음 알게 됐다 :)

댓글 보니 indexOf로 0인지 판별하는 것 또한 똑같다고 한다! 대신 contains는 접두사만 걸러내는 것이 아니기 때문에 불가능!