[프로그래머스 고득점 Kit] 전화번호 목록 자바 풀이 및 정답

프로그래머스 고득점 Kit 해시 분류의 "전화번호 목록"이라는 문제입니다.

 

문제요약)

- 전화번호 여러개가 주어짐

- 그 중 어떤 전화번호가 다른 전화번호의 접두사면 false, 아니면 true 리턴

 

주의점)

- 시간복잡도 고려(phone_book의 길이가 100만이어서 O(n2)시 시간초과 위험)

- 포함여부가 아닌, "접두사" 여부 판단

 

풀이 방법)

1. 단순 무식하게 for문 두번 돌리면서 비교 O(n2). -> 2022년까지 되던 방법이었으나 현재 효율성 기준을 보완한것으로 보임. 이 방법으로 진행 시 효율성 테스트 통과x

2. 문자열 정렬 특성을 활용해서 정렬 후 해시값 비교

 

1번 방법은 사실 잠깐이라도 되었던게 이상할 정도의 문제로 보입니다. 2번으로 풀이하시면 되겠습니다.

 

정답 코드)

여기서 해당 문제를 보면서 정렬을 떠올리려면 숫자로 된 문자열의 정렬 기준을 알고 있어야 확신을 갖고 풀 수 있습니다. 저도 저 부분을 떠올리지 못하고 O(n2)의 풀이방법만 떠올리고 있었기 때문에 문자열 정렬 기준에 대한 글을 추가적으로 첨부하겠습니다.

 

 

 

 

숫자로 되어있는 문자열의 정렬 기준(전화번호 목록 문제 부가 설명)