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

2023. 9. 12. 23:54· Algorithm/Programmers

처음 풀었던 방법인데 효율성 테스트 3,4 에서 시간초과가 뜬 코드다

def solution(phone_book):
    p = []
    answer = True
    for num in sorted(phone_book, key = lambda x: len(x)):
        for prefix in p:
            if num[:len(prefix)] == prefix:
                answer = False
        else:
            p.append(num)
        
        if not answer:
            break

    return answer

startswith 도 써보고, 길이로 정렬이 아닌 그냥 문자열 정렬을 해주기도 했지만

계속 시간 초과가 나서

풀이 과정에 뭔가 생각의 전환이 필요함을 느꼈다!!

참고로 문자열 숫자 정렬은 숫자 크기가 아닌, 앞의 글자 숫자 크기로 정렬을 한다(내림차순이 디폴트)

ex) 119 1191231231 120 이렇게 정렬됨(1'1' > 1'2')

 

def solution(phone_book):
    phone_book.sort()
    answer = True
    
    # i+1의 prefix는 아닌데 i+2의 prefix 일 수는 없음!
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            answer = False
            break

    return answer

이중 for문으로 전체를 검사할 필요 없이 i와 i+1만 비교해주면 된다는 사실을 깨달았다.

 

 

시간 복잡도

정렬(합병정렬): O(nlogn)

for: O(n)

=> O(nlogn)

 

다른 사람 풀이

- zip을 이용해 i와 i+1을 깔끔하게 도출해 냈다.

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

-해시를 이용한 정석 풀이

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 and temp != phone_number:
                answer = False
    return answer

핸드폰 번호를 일단 dict에 key로 다 넣는다.

그리고 다시 for문 돌면서 전화번호의 숫자 하나씩 추가하며 dict으로 검색한다. -> O(1)

'Algorithm > Programmers' 카테고리의 다른 글

[프로그래머스/Python] 베스트앨범  (0) 2023.09.13
[프로그래머스/Python] 의상  (0) 2023.09.12
[프로그래머스/Python] 뒤에 있는 큰 수 찾기  (0) 2023.09.05
[프로그래머스/Python] 스택/큐  (0) 2023.09.05
[프로그래머스/Python] 짝지어 제거하기  (0) 2023.09.05
'Algorithm/Programmers' 카테고리의 다른 글
  • [프로그래머스/Python] 베스트앨범
  • [프로그래머스/Python] 의상
  • [프로그래머스/Python] 뒤에 있는 큰 수 찾기
  • [프로그래머스/Python] 스택/큐
빵빵0
빵빵0
(아직은) 공부하고 정리하는 블로그입니다.
빵빵0
Hack Your World
빵빵0
전체
오늘
어제
  • 분류 전체보기 (79)
    • Error Handling (7)
    • Project (5)
    • Computer Science (4)
      • Data Structure (2)
      • Database (1)
      • Cloud (0)
      • OS (0)
      • Infra, Network (1)
      • AI (0)
    • Language (4)
      • Go (3)
      • Rust (1)
      • Python (0)
      • Java (0)
    • Algorithm (39)
      • BaekJoon (18)
      • Programmers (7)
      • LeetCode (6)
      • NeetCode (8)
    • SW Books (9)
      • gRPC Up & Running (1)
      • System Design Interview (2)
      • 스프링 입문을 위한 자바 객체지향의 원리와 이해 (6)
      • 블록체인 해설서 (0)
      • 후니의 쉽게 쓴 CISCO 네트워킹 (0)
    • Own (3)
      • Personal (1)
      • Novel (0)
      • Memo (2)
    • BlockChain (4)
      • Issues (0)
      • Research (4)
      • Tech (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Palindrome
  • DP
  • blockchain
  • BFS
  • 프로그래머스
  • Python
  • Programmers
  • 블록체인
  • ohlcv
  • go
  • Hash Table
  • 백준
  • BaekJoon
  • two pointer
  • 스택
  • 그리디
  • Greedy
  • LeetCode
  • BEAKJOON
  • Event
  • chart
  • candlechart
  • 해시
  • MongoDB
  • NeetCode
  • 큐
  • golang
  • decimal
  • KBW
  • 2024

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
빵빵0
[프로그래머스/Python] 전화번호 목록
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.