문제
https://school.programmers.co.kr/learn/courses/30/lessons/42577
풀이
이 문제는 "해시" 카테고리에 있지 않았다면 못 풀었을 것 같은 문제였다고 생각한다.
성능 테스트를 통과하려면, HashMap의 탐색 시간 복잡도가 O(1) 인 것을 최대한 이용해야 한다.
그럼 HashMap의 key, value를 무엇으로 정해야 할까?
=> 전화번호의 substring을 key, 전화번호의 길이를 value로 잡고 모두 저장하면, 전화번호가 다른 전화번호의 접두어인지 O(1)로 확인할 수 있다.
1. 모든 전화번호에 대해 <key: substring값, value: substring의 본래 전화번호 길이>를 HashMap에 저장한다.
substring이 동일한데, 전화번호 길이가 더 길다면, 값을 갱신한다. => O(n * 20)
2. phone_book 배열을 순회하며 HashMap에서 본래 전화번호 길이를 꺼내 비교한다. 전화번호 길이가 자신보다 더 길다면 접두어가 존재하는 것이므로, return false. => O(n)
import java.util.HashMap;
class Solution {
//무식한 방법: O(nlogn + n^2)
//HashMap 사용: O(20n)
public boolean solution(String[] phone_book) {
boolean answer = true;
HashMap<String, Integer> phoneBook = new HashMap<String, Integer>();
for(String phoneNumber: phone_book) {
for(int i = 0; i < phoneNumber.length(); ++i) {
String subStr = phoneNumber.substring(0,i);
if(phoneBook.get(subStr) == null) {
phoneBook.put(subStr, phoneNumber.length());
} else {
if(phoneNumber.length() > phoneBook.get(subStr)) {
phoneBook.put(subStr, phoneNumber.length());
}
}
}
}
for(String phoneNumber: phone_book) {
if(phoneBook.get(phoneNumber) != null && phoneBook.get(phoneNumber) > phoneNumber.length()) return false;
}
return answer;
}
}
'Algorithm > Programmers' 카테고리의 다른 글
프로그래머스 42586번 기능 개발 (0) | 2022.08.08 |
---|---|
프로그래머스 42579번 베스트앨범 (0) | 2022.07.31 |
프로그래머스 42578번 위장 (0) | 2022.07.26 |
프로그래머스 42576번 완주하지 못한 선수 (0) | 2022.07.16 |
프로그래머스 1845번 폰켓몬 (0) | 2022.07.16 |