[코딩테스트] Programmers - 전화번호 목록 (실패)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

 

풀이 1

문제 = 한 번호가 다른 번호의 접두어인 경우가 있는지 확인 
ex) 
구조대 = 119
박준영 = 97 674 223
지영석 = 11 9552 4421
-> 구조대의 번호가 지영석의 번호의 접두사이다. 

입력
- 전화번호 담은 배열 phone_book

출력
- 어떤 번호가 다른 번호의 접우어인 경우가 있다 = false 반환
- 없다 = true 반환

제한 사항
- 1 <= phone_book 길이 <= 1,000,000
    - 1 <= 전화번호 길이 <= 20
    - 같은 전화번호 중복 없다. 

풀이 1
- 119가 다른 전화번호에 포함되어 있는지 확인하려면 
    다른 전화번호를 하나씩 탐색해서 그 번호에 119가 포함되어 있는지 확인하면 된다. 
- 그걸 어떻게 구현할까인데
- A번호에 B번호가 있는지 확인. 

가장 쉬운 방법은 이중 for문을 써서 
i번째 번호가 i+1~n번째 번호에 포함되어 있는지 확인하는 방법 
시간복잡도는 O(N^2) = O(100만 제곱) = 1,000,000,000,000 = 1초 넘는다. 
이중 for문 방법 사용하면 안 된다. 

문제 유형이 해시이니 Dictionary로 풀어야 하는데.
일단 phone_book 원소들을 딕셔너리에 다 넣어보자. 그리고.. 어떻게 풀지 전혀 모르겠다. 

다른 사람 풀이를 보자. 

 

 

풀이 2 

문자열 배열을 사전순으로 정렬하고, 문자열 배열에서 인접한 원소끼리 비교해서 풀면 된다. 

 

❓크기 순서대로 정렬을 하더라도 i번째와 i+1번째, i번째와 i+2번째를 비교해야 할 텐데, 왜 인접한 원소끼리 비교해서 풀어도 될까? 

 

문자열 배열을 사전순으로 정렬하면
A가 C의 접두어라면, A바로 옆에 있는 B도 A를 접두어로 가진다. 따라서 A는 바로 옆에 있는 문자열과 비교해도 A가 누군가의 접두어가 되는 것을 검사할 수 있다. 

 

 

코드 1 - 정답 (C#)

public bool solution(string[] phone_book)
{
    Array.Sort(phone_book); // 사전 순 정렬

    // 인접한 원소끼리 비교 
    for(int i = 0; i < phone_book.Length - 1; i++)
        // phone_book[i]가 phone_book[i+1]에 포함되어 있으면
        if(phone_book[i+1].StartsWith(phone_book[i])) 
            return false;

    // 여기까지 왔다는 건 한 번호가 다른 번호의 접두사인 경우가 없다는 것 
    return true; 
}

 

 

코드1 - 정답 (Java)

import java.util.Arrays;

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;
    }
}

 

 

효율성 테스트에서 시간이 꽤 걸린다. 

 

 

풀이 3

해시 문제이니 딕셔너리로 풀 수도 있다. 

딕셔너리에 phone_book 문자열들을 넣고, 딕셔너리 키값을 하나씩 뽑아서 이 키값의 접두사를 전화번호로 하는 것이 딕셔너리에 있는지 확인하고 있으면 false를 없으면 true를 반환하면 된다. 

 

 

코드 2 - 정답 (C#)

public bool solution2(string[] phone_book)
{
    // 딕셔너리 사용
    Dictionary<string, int> dict = new Dictionary<string, int>();

    // 딕셔너리에 phone_book 저장  
    foreach(string key in phone_book)
        dict[key] = 1;

    // phone_book[i]의 접두사를 번호로 하는 얘가 딕셔너리에 있는가 
    foreach(string key in phone_book)
        for(int i = 1; i < key.Length; i++)
            if(dict.ContainsKey(key.Substring(0, i)))
                return false;

    return true;
}

 

코드2 - 정답 (Java)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) 
    {
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < phone_book.length; i++)
            map.put(phone_book[i], 1);
        
        for(int i = 0; i < phone_book.length; i++)
            for(int j = 1; j < phone_book[i].length(); j++)
                if(map.containsKey(phone_book[i].substring(0, j)))
                    return false;
        return true;
    }
}

 

 

효율성 테스트는 배열을 사용한 방법보다 시간이 덜 걸린다. 

 

 

cf) 

 

 

복습 1 풀이 (6/7)

[문제]
한 번호가 다른 번호의 접두어인 경우가 있는지 확인하기. 
전화번호 담은 배열 phone_book이 주어진다. 
어떤 번호가 다른 번호의 접두어가 있으면 false 
어떤 번호가 다른 번호의 접두어가 없으면 true를 반환하라. 

[제한 사항]
- 1 <= phone_book 길이 <= 1,000,000
- 1 <= 전화번호 길이 <= 20 
- 같은 전화번호는 중복 저장 X 

[풀이]
당장 떠오르는 풀이는 phone_book[i]가 phone_book[i+1], phone_book[i+2], ... 과 비교했을 때
접두어가 있는지 확인하기. 
이중 for문 > O(N^2)
N은 최대 1,000,000. > O(100만 제곱) = 1,000,000,000,000 = 1초 넘는다 > 시간 초과 

다른 풀이 생각해야 한다. 

방법1
- 문자열 배열을 정렬한다. 
- 문자열 배열을 정렬하면, 앞 문자가 작은 순서대로 정렬이 된다. 
- 그러면 phone_book에서 바로 가까이 있는 문자열들은 접두어 관계에 있을 수 있다. 
- 뒤에 문자열들은 볼 필요가 없다. 이미 문자열 정렬이 되었으므로, 가까운 문자열끼리 비교하면 된다. 

방법2
해시 문제인 만큼 해시로 풀어보자. 
- 일단 phone_book 원소들을 딕셔너리(dict)에 넣자. 
    - 전화번호는 중복되지 않는다고 했으니, value는 1로 넣으면 된다. 
- phone_book[i]를 하나씩 검사해서 phone_book[i]의 접두사가 전화번호인 것을 dict에서 찾으면 된다. 

 

 

코드 1 - 정답

public bool solution(string[] phone_book)
{
    Array.Sort(phone_book); 
    for(int i = 0; i < phone_book.Length - 1; i++)
    {
        // phone_book[i]가 phohe_book[i+1]에 포함되어 있는가? 
        if(phone_book[i+1].StartsWith(phone_book[i]))
            return false;
    }

    return true;
}

 

 

코드 2 - 정답

public bool solution(string[] phone_book)
{
    Dictionary<string, int> dict = new Dictionary<string, int>();
    foreach(string key in phone_book)
    {
        if(!dict.ContainsKey(key))
            dict.Add(key, 1);
    }

    foreach(string key in phone_book)
    {
        for(int i = 1; i < key.Length; i++)
        {
            if(dict.ContainsKey(key.Substring(0, i)))
            return false;
        }
    }
    return true;
}