전화번호 목록

내 풀이

난 아래와 같은 방법으로 문제를 풀었는데 효율성 테스트에서 실패했다.

def start_with(prefix:str, compare:str):
  for i in range(len(prefix)) :
    if prefix[i] != compare[i] : 
      return False
    
  return True
 
def solution(phone_book):
  while phone_book : 
    cur = phone_book.pop()
    for p in phone_book : 
      if len(p) > len(cur) :
        if start_with(cur, p) :
          return False
      else :
        if start_with(p, cur) :
          return False
        
  return True

다른 사람 풀이

Python - Hash

해당 문제 풀이의 순서는 다음과 같다.

모든 전화번호를 hash_map에 저장한다.
모든 전화번호를 다시 순회하면서 한 글자 한 글자 올려가며 hash_map에 있는지 확인한다. prefix란 무엇인가에 대한 생각을 조금 깊게 해봤다면 도출해낼 수 있는 풀이였던 것 같다.
하지만 이렇게 할 경우 가장 오래 걸리는 경우 2 * 1,000,000 + 19 정도의 시간 복잡도를 가지게 되고 그렇게 효율적인 방법이란 생각은 들지 않는다.

def solution(phone_book):
  answer = True
  hash_map = {}
  for phone_number in phone_book:
    hash_map[phone_number] = 1
  for phone_number in phone_book:
    temp = ""
    for number in phone_number:
      temp += number
      if temp in hash_map :
        if temp != phone_number :
          answer = False
  return answer

CPP - Sort

문제 풀이 아이디어는 일단 정렬을 해놓으면 반드시 리스트의 앞에 있는 문자가 뒤에 있는 문자의 prefix가 되거나 아니면 아예 되지 못한다는 전제로 문제를 푸는 것이다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool startsWith(const string &str, const string &prefix) {
    return str.size() >= prefix.size() && str.substr(0, prefix.size()) == prefix;
}
 
bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    if(phone_book.size() == 1) return true;
    
    for(int i = 0; i < phone_book.size()-1; i++) {
        auto& c = phone_book[i];
        auto& n = phone_book[i+1];
        if(startsWith(n, c)) return false;
    }
    return true;
}

폰켓몬 가장 큰 수