[Programmers/프로그래머스] #2. 전화번호 목록 JAVA

문제 설명

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

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

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

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다

입출력 예제

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

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

나의 풀이

사용언어 : java

[1] 문제 분석

처음에 문제를 받았을 때 시간복잡도에 대해서 고민을 많이 했다. 이전 문제는 for문을 단일로 써 시간복잡도를 최소화 했다면

이번문제에서는 필수불가결로 이중for문을 쓸 수 밖에 없었다. 대신 복잡도를 최소한으로 줄이기 위해서 한번 탐색한 배열값은

다시 탐색하지 않도록 하였고 접두어를 찾는 즉시 return을 하게 만들었다.

class Solution {
    public boolean solution(String[] phone_book) {
       
        for(int i=0; i<phone_book.length;i++)
        {
            for(int j=i+1;j<phone_book.length;j++) {
                if(phone_book[j].startsWith(phone_book[i]))
                    return false;
            }
        }
        return true;
    }
}

startsWith 함수는 캐릭터라인이 지정된 문자열로 접두사가 시작되는지 아닌지를 리턴해주는 함수이다.

함수같은 경우 어떤 함수가 있는지 모르는 경우가 있다. 이럴때는 oracle사의 java api를 참고하면 된다.

https://docs.oracle.com/javase/9/docs/api/java/lang/String.html#startsWith-java.lang.String-

String (Java SE 9 & JDK 9 )

 

하지만 위의 코드가 완벽하다고 생각하고 실행을 눌렀더니.....

 

위와같이 몇개의 테스트에서 실패를 하는 현상을 볼 수 있다.

[2] 문제 풀이

 프로그래머스의 테스트 실패의 원인을 보자면 다음과 같다.

1) 입출력 예제로는 통과했지만 다른 테스트케이스에서 코드가 통과되지 않는다 => 코드설계의 오류

2) 테스트케이스의 예제를 돌리는데 시간복잡도가 많이 걸린다.

나의 경우는 1번에 해당되었다. 테스트케이스를 보지 못해 어떤 부분에서 에러가 나는지 몰라 고민했는데 

문득 나의 코드의 경우는 a ->b를 비교하는 것은 있어도 b->a를 비교하는것이 없었다.

예)1541->154, 154->1541

때문에 이러한 테스트코드에서 오류가 나는것으로 추정했다.

그래서 Arrays.sort()함수로 배열을 정렬해주고 돌려보았다.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);       
        for(int i=0; i<phone_book.length;i++)
        {
            for(int j=i+1;j<phone_book.length;j++) {
                if(phone_book[j].startsWith(phone_book[i]))
                    return false;
            }
        }
        return true;
    }
}

 

테스트 올클리어..... 완벽히 통과가 되었다.