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

[문제 설명]

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

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

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

 

[입출력 예]

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

 

[차근 차근 생각해보기]

1. set에 전화번호를 넣어준다.
2. phone_book 배열을 돌면서 phone_book 원소를 0부터 i번째까지 잘라준다.
3. 자른 것이 set에 포함 되어 있으면 false를 리턴해준다.    

 

[코드]

<수정전>

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length - 1; i++) {
            String s = phone_book[i];
            if (phone_book[i + 1].startsWith(s)) {
                return false;
            }
        }
        return answer;
    }
}

 

<수정후>

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet();
        for (String phone : phone_book) {
            set.add(phone);
        }
        
        for (String phone : phone_book) {
            for (int i = 0; i < phone.length(); i++) {
                String prefix = phone.substring(0, i);
                
                if (set.contains(prefix)) {
                    return false;
                }
            }
        }
        
        return true;

    }
}

 

[반성할 점]

처음엔 이중 반복문으로 풀려고 했는데 계속 답이 안 맞고, 시간초과가 났다.😭

다음엔 phone_book 배열을 정렬한 뒤 i+1번째 원소가 i번째 원소로 시작하면 false를 리턴해주는 방법으로 풀었었다. 

 

그리고 나는 항상 풀고 나선 개발자 지인에게 항상 코드 수정할 것은 없는지,

효율적인 방법은 없는지, 풀면서 모르는 것들을 물어보는 습관이 있다. 

 

나름 뿌듯하게 풀었다며 코드를 보여주었고, 풀면서 시간초과가 나는 이유에 대해서도 물어보았다.

정렬해서 푸는 방법보다는set을 사용하여 푸는 것이 효율적이라고 이야기해 주었다.

이유는 제한사항에 phone_book 배열의 길이는 1이상 1,000,000이하 이고 이럴 경우 이중 반복문을 돌게 되면 시간 초과가 난다고 하였다.

이를 해결하기 위해선 hash를 사용해야 한다고 했다. 

 

hash는 하나하나 돌면서 그 값을 찾는 게 아닌 일치하는 값이 있으면 바로 이동한다고 하였다.

(잘못된 정보면 지적부탁드립니다. 지적은 언제든지 환영입니다!) 

 

그다음 phone_book 배열 원소 하나를 0번째에서 i번째까지 substring으로 잘라 set에 포함되어 있는지 비교하면 된다고 하였다.

 

아직까지 이렇게 논리적으로 생각하는 게 많이 부족하다ㅠ

그리고 이제는 자료구조를 공부해야 할 때인 것 같다..