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

 

[21-05-29]

비교적 익숙한 해시..!!

한번에 퍼펙트하게 풀진 못했지만 그래도 다른 알고리즘 문제보단 비교적 빠르게 풀었다

 

---

문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

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

 

입출력 예

[phone_book]	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

 

 

풀이

 

통과 실패 코드

import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        int minSize = 9999;
        for(String phone : phone_book) {
            if(minSize > phone.length() ) {
                minSize = phone.length();
            }
        }
        
        HashSet<String> hash = new HashSet<String>();
        for(String phone : phone_book) {
            hash.add( phone.substring(0, minSize) );
        }
        
        if(hash.size() < phone_book.length) {
            answer = false;
        }
        
        return answer;
    }
}

 

위 코드는 [코드 실행]으로 테스트 가능한 케이스 3개는 모두 통과하고,

아래와 같이 제출에서 11번, 14번 테스트케이스를 통과하지 못한다🤪

 

 

위 코드는 중복을 허옹햐지 않는 Set에 앞자리 일부를 잘라 넣은 다음,

set의 size를 원본과 비교하여 같지 않으면 겹친 것들이 있겠다고 생각하여 짠 코드당.

가장 작은 글자수를 굳이 선택했던 것 또한

큰 자리수 보단 작은 자리수가 다른 원소에 포함 될 확률이 높았을거라고 생각했다... But... It is....😂

 

 

11번과 14번 케이스가 뭔진 모르겠지만 코드를 수정하던 중 다음과 같은 결함이 있는 것을 발견했다.

 

 

* 테스트 케이스 - phone_book ["123", "1197", "557713", "11987543"] / true

위 케이스는 가장 작은 글자수 만큼 잘려진 글자는 같지만, 전체 글자를 비교 하면 겹치지 않는 상황이다.

 

짜여진 코드는 phone_book에서 가장 작은 글자수를 가진 원소 "123"의 length 3을 기준으로,

모든 글자의 앞머리 3글자를 잘라 판단한다.

이때"1197"과 "11987543"이 같다고 결과가 나올 것이다.

1197이 11987543 포함 되지 않음에도, 앞 3자리를 잘라 비교하면 119, 119로 같다고 판단하기 때문이다.

 

 

통과 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        int minSize = 9999;
        for(String phone : phone_book) {
            if(minSize > phone.length() ) {
                minSize = phone.length();
            }
        }
        
        Arrays.sort(phone_book);
        
        HashMap<String, String> hash = new HashMap<String, String>();
        for(String phone : phone_book) {
            String key = phone.substring(0, minSize);
            
            // 제일 작은 글자수 만큼 잘랐는데 이미 있음. 있는 경우 비교를 통해 전체가 동일한지 판단 
            if(hash.containsKey(key)) {
                String value = hash.get(key);
                if(phone.startsWith(value)) {
                    answer = false;
                    break;
                }
            }
            hash.put( key, phone );
        }
        
        return answer;
    }
}

 

통과

 

그래서 앞자리가 겹쳐 접두어 포함관계가 의심되는 경우 접두어를 판단해주는

startsWith(str) 함수를 사용하여 판단해주었다.

startsWith() 함수도 String method를 찾아 보다가 얻어 걸린 건데

다들 이 메소드를 사용해서 많이 푸는 것 같았다. 얻어 걸려 다행쓰😁

 

 

일단 함 startsWith 함 써보자! 하고 기존 코드에 추가만 하고 테스트 해보다 통과한건데

저 메소드를 쓰면 앞자리 잘라서 안해도 될듯.

 

 

 

 

+

따로 추가한 테스트 케이스

["4321", "432", "122", "1334"] / false
["119", "123192", "88838333", "1234", "123200"] / true
["99", "1234", "1947", "8671", "12122", "19478", "787486"] / false