🤔 문제
🔗
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
👊 풀이과정
가장 간단한 방법으로 이중 for문을 사용해 배열의 요소 하나하나를 서로 매치하는 방법도 있겠다.
하지만 이렇게 하면 시간복잡도가 O(N^2)가 되어 효율성이 떨어진다.
가능한 반복문을 한번만 사용하는 방법을 생각해보았다.
우선 sort()를 사용해 배열을 순차적으로 정렬한다.
Arrays.sort(phone_book);
배열을 정렬한 이유는 비교를 간편하게 하기 위해서이다.
배열의 한 요소는 다음 요소들의 접두어가 될 수도 있고 아닐수도 있다.
그러나 이전 요소의 접두어가 되는 것은 불가능하다. 배열이 정렬된 상태이기 때문이다.
따라서 비교는 한 요소를 기준으로 그 다음 요소들과 해주어야 한다.
한편 한 요소를 바로 다음 요소와 비교했을 때, 접두어 관계가 성립하면 더이상 탐색할 필요가 없이 false를 리턴하면 된다.
그러나 접두어 관계가 성립하지 않으면 해당 요소는 그 다음에 오는 그 어떤 요소의 접두어도 될 수 없다.
따라서 결론적으로 비교는 한 요소를 기준으로 바로 다음 요소와 해주어야 한다.
이에 따라 다음과 같은 반복문을 작성할 수 있다.
특정 요소가 다른 요소의 접두어가 되는지 판단하기 위해 startsWith()를 사용했다.
for(int i=0 ; i<phone_book.length-1 ; i++) {
if(phone_book[i+1].startsWith(phone_book[i])) {
return false;
}
}💻 소스코드
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;
}
}