hash

프로그래머스: 전화번호 목록 (파이썬, hash, dictionary)

hash문제이다. 자바에서는 해시값을 사용하는 자료형이 hashmap이고 파이썬에서는 dictionary이다. 내가 푼 문제가 아닌건 블로그에 기록하지 않는데 풀이가 너무 좋아서 내 나름의 수정을 더해 코드와 깨달은 점을 올려본다. 전화번호부가 10^6이기에 완전탐색을 하면 시간복잡도가 O(n^2)이므로 10^12이 되어 시간초과가 날 것 같았다. 따라서 처음에 푼 풀이는 비교하려는 수보다 큰 수일때만 접두사가 될 수 있다는 점, 비교하려는 수보다 값이 커지면 더 비교를 할 필요가 없다는 점을 이용해 반복문에 조건문을 추가하여 탐색을 중간에 멈추게 함으로써 시간복잡도를 nO(logn)으로 만들어 6*10^6으로 풀려고 시도했으나 보기좋게 마지막시도에서 계속 시간초과가 났다. 예를 들어 [121, 83, ..