[PCCP] Lv2: 전화번호 목록(42577) 해설

문제

- 문제 링크: 전화번호 목록

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: phoneBook의 길이

- sort(): O(NlogN)

- 반복문은 N번 수행하고 각 substr()은 전화번호 길이만큼 수행할 수 있으므로 전화번호 길이가 M이라면 반복문의 총 시간 복잡도는 O(N*M)

- N이 M보다 크므로 M을 상수화하면 반복문의 총 시간 복잡도는 O(N)

- 총 시간 복잡도는 O(NlogN)

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

bool solution(vector<string> phoneBook) {
    // 전화번호 목록을 오름차순으로 정렬
    sort(phoneBook.begin(), phoneBook.end());
    
    // 모든 전화번호를 순회하며 다음 번호와 비교
    for (int i = 0; i < phoneBook.size() - 1; ++i) {
        // 현재 번호가 다음 번호의 접두어이면 false
        if (phoneBook[i] == phoneBook[i + 1].substr(0, phoneBook[i].size())) {
            return false;
        }
    }
    // 어떤 번호도 다른 번호의 접두어가 아니면 false
    return true;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: phone_book의 길이

- phone_book을 정렬하는 시간 복잡도: O(NlogN)

- phone_book의 길이만큼 반복문을 순회하고 내부에 있는 startwith() 메서드는 문자열의 길이에 비례하는 연산을 수행

- 문자열의 길이는 20이므로 상수 처리

- 최종 시간 복잡도: O(NlogN) + O(N) → O(NlogN)

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;
        }
        
        // 모든 전화번호를 비교한 후에도 반환되지 않았다면, 접두어가 없는 경우이므로 true 반환
        return true;
    }
}

solution 2) 해시셋을 이용한 풀이

- M: 전화번호의 길이. 최대 20

- 최종 시간 복잡도: O(N * M)

- 전화번호의 길이가 짧으므로 상수처리하여 O(N)으로 볼 수 있음

- 최악의 경우 1000,000 * 19 = 19,000,000

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        // phone_book 배열의 값을 해시셋에 저장
        HashSet<String> set = new HashSet<>(Arrays.asList(phone_book));
        
        for (String s: phone_book) {
            // 현재 String s보다 기링가 더 짧은 String이 set에 있는지 확인
            for (int i = 1; i < s.length(); ++i) {
                if (set.contains(s.substring(0, i)))
                    return false;
            }
        }
        return true;
    }
}

solution 3)

#include<>

 

(Python)

solution 1)

- N: phone_book의 길이

- phone_book 정렬 : O(NlogN)

- phone_book의 길이만큼 반복문을 순회하고 내부에 있는 startswith() 메서드는 문자열의 길이에 비례하는 연산을 수행

- 문자열의 길이는 20이므로 상수 처리

- 총 시간 복잡도: O(NlogN) + O(N)

- 최종 시간 복잡도: O(NlogN)

def solution(phone_book):
    # 전화번호부 정렬
    phone_book.sort()
    
    # 전화번호부에서 연속된 두 개의 전화번호 비교
    for i in range(len(phone_book) - 1):
        if phone_book[i + 1].startswith(phone_book[i]):
            return False
    
    # 모든 전화번호를 비교한 후에도 반환되지 않았다면, 접두어가 없는 경우이므로 True 반환
    return True

solution 2)

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True

solution 3)

import

 

(JavaScript)

solution 1)

- N: phone_book의 길이

- phone_book을 정렬하는 시간복잡도: O(NlogN)

- startsWith()은 문자열의 길이에 비례하는 연산을 수행

- phone_book의 길이만큼 반복문을 순회: O(N)

- 총 시간복잡도: O(NlogN + N)

- 최종 시간 복잡도: O(NlogN)

function solution(phone_book) {
    phone_book.sort() // 전화번호부 정렬
    
    // 전화번호부에서 연속된 두 개의 전화번호 비교
    for (let i = 0; i < phone_book.length - 1; i++) {
        if (phone_book[i + 1].startsWith(phone_book[i])) {
            return false;
        }
    }
    
    // 모든 전화번호를 비교한 후에도 반환되지 않았다면, 접두어가 없는 경우이므로 true 반환
    return true;
}

solution 2)

import

solution 3)

import