문제
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 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 |
1차 풀이 (2021.01.21)
phone_book을 탐색하며 그 번호로 시작하는 다른 번호가 있는지 탐색한다.
stream을 얼마 전에 공부해서 그런지 바로바로 써먹을 수 있었다. 스트림 최고 편하고 좋다.
코드
import java.util.Arrays;
class Solution {
public boolean solution(String[] phone_book) {
for (String phone : phone_book)
if (Arrays.stream(phone_book).anyMatch(number -> !number.equals(phone) && number.startsWith(phone))) return false;
return true;
}
}2차 풀이 (2021.08.24)
stream을 사용했더니 효율성에서 빠꾸먹었다.
당연하다. stream을 사용해서 검사하면 시간복잡도가 O(N^2)일 뿐더러, stream을 생성하는 비용도 크다.
그래서, 정렬을 먼저 하고 서로 붙어 있는 것들끼리만 검사하도록 했다.
해시라는 카테고리에 갇혀 생각할 필요가 없는 것 같다.
코드
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
for (int i=0 ; i<phone_book.length-1 ; i++) {
if (phone_book[i+1].startsWith(phone_book[i])) {
return false;
}
}
return true;
}
}