문제

문제 분석

현재 전화번호의 부분집합(전체가능)이 다른 전화번호와 일치하는지 점검하는 문제입니다.

---

풀이

문제에서 의미하는 접두어가 무엇인지 파악하는것이 정답과 상당히 깊은 관련이 있는 문제입니다. 뒷부분은 신경쓰지 않고 앞부분만 일치여부를 확인하므로 앞에서 부터 차례로 비교합니다.

순서

1. 전화번호를 컬렉션에 저장
2. 전화번호의 부분집합으로 비교

전화번호를 컬렉션에 저장

간단하고 컬렉션이 정해진것은 아니지만 해시맵으로 구현하였습니다.

		boolean answer = true;
        
        HashMap<String,Integer> hashmap = new HashMap<>();
        for(int i=0;i<phone_book.length;i++){
            hashmap.put(phone_book[i],i);
        }

전화번호의 부분집합으로 비교

		for(int i=0;i<phone_book.length;i++){
            for(int j=1;j<phone_book[i].length();j++){
                if(hashmap.containsKey(phone_book[i].substring(0,j)))
                    answer = false;
            }
        }

substring()으로 한자리부터 마지막자리까지 점진적으로 늘려가며 해시맵.containsKey()로 다른 전화번호와 비교하였습니다.

---

코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        // 중복을 허용하지 않는 컬렉션으로 전화번호를 저장
        Set<String> set = Arrays.stream(phone_book).collect(Collectors.toCollection(HashSet::new));
        
        //전화번호 하나씩
        for(int i = 0; i < phone_book.length;i++){
            for(int j = 0; j < phone_book[i].length();j++) //접두어 비교
                //접두어가 다른 전화번호에 존재하면 false
                if(set.contains(phone_book[i].substring(0,j))) answer = false;
        }
        return answer;
    }
}

---

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%9E%90%EB%B0%94/Level2/%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8%EB%AA%A9%EB%A1%9D.java