프로그래머스 전화번호 목록 자바 문제풀이

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

 

위 문제는 String 배열인 phone_book을 주는데

배열 중 하나의 인덱스가

다른 인덱스의 접두어인 경우에는

false를 반환하고 그 외에는 true를 반환한다

 

여기서 접두어가 뭔 말이냐면

119 / 97674223 / 1195524421 가 있을 때

1195524421 앞에 119가 있는 것이 보이는데

배열 안에 119가 존재하기 때문에

 

한 번호가 다른 번호의 접두어라고

보고 false를 반환하면 된다

 

유의할 점은 대량의 데이터를 가지고

조회를 수행할 경우 startsWith / equals 등은

속도가 느리기 때문에(효율성에서 걸림)

해시를 이용한 방법으로 문제를 풀어줘야 한다

---

문제풀이는 HashSet 안에 배열 데이터를 담아준 뒤

for 문을 두번 돌리는 것으로

깔끔하게 해결할 수 있는데

 

먼저 set 크기만큼 for 문을 돌려주면서

set의 값 하나씩 꺼내준 뒤 

다시 해당 값의 length로 for 문을 돌리면서

set에 contains가 되어있는지 확인하는 것인데

 

길이가 긴 값을 한글자씩 분해하면서

자른 값이 자기가 아니면서(hashCode)

(equals를 쓰지 않는 이유는 효율성 때문)

 

set 안에 contains 되어 있다면

해당 값이 지금 for 돌리고 있는 값의

접두어로 사용되고 있기 때문에

바로 return false를 해주고

 

그 외에는 접두어가 없기 때문에

true를 return 시켜주면 된다

 

이 이중 for 문의 핵심은 큰 값을 분해하면서

작은 값이 접두어에 해당되는지를

contains로 찾아주면 된다

 

마지막으로 답안에 사용한 코드는 아래와 같다

 

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashSet<String> set = new HashSet<>(Arrays.asList(phone_book));

        for(String val : set) {
            for(int i = 1; i<=val.length(); i++) {
                // set의 값을 가지고 for 문을 돌리면서 접두어에 해당되는 값 찾기(contains)
                // 본인이 본인의 접두어가 되는 경우는 제외처리(hashcode)
                if(set.contains(val.substring(0, i)) && val.substring(0, i).hashCode() != val.hashCode()) {
                    return false;
                }
            }
        }

        return answer;
    }
}