[Algorithm] 문제풀이 - 해시-5
2. 전화번호 목록
- 전화 번호를 담은 배열 phone_book이 solution 함수의 매개 변수로 주어질 때,
- 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 그렇지 않으면 true를 리턴
입출력
- 입력 : 전화 번호를 담은 배열 phone_book
- 출력 : 접두어인 경우가 있으면 false 그렇지 않으면 true
제한 사항
- phone_book의 길이는 1이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하 입니다.
- 같은 전화번호가 중복 해서 들어있지 않습니다.
Brute force
public boolean solution(String[] phone_book) {
for (int i = 0; i < phone_book.length; i++) {
for (int j = 0; j < phone_book.length; j++) {
if (i == j) continue;
String shorter = phone_book[i].length() <= phone_book[j].length() ? phone_book[i] : phone_book[j];
String longer = phone_book[i].length() > phone_book[j].length() ? phone_book[i] : phone_book[j];
if (longer.startsWith(shorter)) {
return false;
}
}
}
return true;
}
실행 결과
정확성 테스트
테스트 1 〉 통과 (0.02ms, 77.2MB)
테스트 2 〉 통과 (0.04ms, 70MB)
테스트 3 〉 통과 (0.02ms, 74.8MB)
테스트 4 〉 통과 (0.02ms, 70.2MB)
테스트 5 〉 통과 (0.03ms, 75.4MB)
테스트 6 〉 통과 (0.02ms, 79.4MB)
테스트 7 〉 통과 (0.02ms, 66.3MB)
테스트 8 〉 통과 (0.02ms, 76.7MB)
테스트 9 〉 통과 (0.02ms, 72.8MB)
테스트 10 〉 통과 (0.01ms, 75.5MB)
테스트 11 〉 통과 (0.02ms, 82.4MB)
테스트 12 〉 통과 (0.02ms, 74.3MB)
테스트 13 〉 통과 (0.02ms, 72.2MB)
테스트 14 〉 통과 (24.44ms, 79.6MB)
테스트 15 〉 통과 (22.02ms, 87.1MB)
테스트 16 〉 통과 (28.23ms, 85.8MB)
테스트 17 〉 통과 (58.80ms, 82MB)
테스트 18 〉 통과 (80.43ms, 84.2MB)
테스트 19 〉 통과 (38.43ms, 89.8MB)
테스트 20 〉 통과 (108.51ms, 79.8MB)
효율성 테스트
테스트 1 〉 통과 (0.03ms, 55.3MB)
테스트 2 〉 통과 (0.03ms, 55.5MB)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
해쉬셋 이용
import java.util.*;
import java.util.stream.*;
class Solution {
public boolean solution(String[] phone_book) {
Set<String> pbSet = new HashSet<>(Arrays.asList(phone_book));
if(pbSet.size() < phone_book.length) return false;
// 전체 length 가져오기
Set<Integer> lenSet = pbSet.stream().map(x -> x.length()).collect(Collectors.toSet());
List<String> list = pbSet.stream()
.sorted(Comparator
.comparing(String::length)
.reversed())
.collect(Collectors.toList());
for(String b : list){
int len = b.length();
//전체 length 단위로 단어 자르기
Set<String> parts = lenSet.stream().filter(x -> x < len).map(y -> b.substring(0,y))
.collect(Collectors.toSet());
//일치하는 단어(접미사)가 있는 지 확인
for(String p : parts){
if(pbSet.contains(p)) {
return false;
}
}
}
return true;
}
}
-
채점결과
채점을 시작합니다. 정확성 테스트 테스트 1 〉 통과 (4.02ms, 76.2MB) 테스트 2 〉 통과 (4.67ms, 78.9MB) 테스트 3 〉 통과 (3.86ms, 78MB) 테스트 4 〉 통과 (5.89ms, 79.1MB) 테스트 5 〉 통과 (5.53ms, 75.4MB) 테스트 6 〉 통과 (6.97ms, 71.4MB) 테스트 7 〉 통과 (4.11ms, 77MB) 테스트 8 〉 통과 (4.85ms, 71.4MB) 테스트 9 〉 통과 (4.02ms, 80.8MB) 테스트 10 〉 통과 (3.98ms, 74.3MB) 테스트 11 〉 통과 (4.40ms, 81MB) 테스트 12 〉 통과 (3.94ms, 76.4MB) 테스트 13 〉 통과 (4.36ms, 78MB) 테스트 14 〉 통과 (16.44ms, 83.3MB) 테스트 15 〉 통과 (10.50ms, 79.7MB) 테스트 16 〉 통과 (11.98ms, 78.4MB) 테스트 17 〉 통과 (12.10ms, 80.8MB) 테스트 18 〉 통과 (16.61ms, 82.3MB) 테스트 19 〉 통과 (14.82ms, 75.9MB) 테스트 20 〉 통과 (19.28ms, 79.4MB) 효율성 테스트 테스트 1 〉 통과 (44.06ms, 57.6MB) 테스트 2 〉 통과 (40.80ms, 56.8MB) 테스트 3 〉 통과 (439.13ms, 152MB) 테스트 4 〉 통과 (447.15ms, 147MB) 채점 결과 정확성: 83.3 효율성: 16.7 합계: 100.0 / 100.0
for문 1번
public boolean solution(String[] phone_book) {
Map<String, Boolean> map = new HashMap<>();
for (String phone : phone_book) {
if (map.containsKey(phone)) {
return false;
}
for (int i = 1 ; i < phone.length(); i++) {
String subNumber = phone.substring(0, i);
if (map.containsKey(subNumber) && map.get(subNumber)) {
return false;
}
// 자기자신은 true, 접두어는 false 로
// 분리된거만 false
map.put(subNumber, false);
}
map.put(phone, true);
}
return true;
}
채점을 시작합니다.
정확성 테스트
테스트 1 〉 통과 (0.05ms, 76.2MB)
테스트 2 〉 통과 (0.04ms, 83.7MB)
테스트 3 〉 통과 (0.03ms, 78.7MB)
테스트 4 〉 통과 (0.03ms, 73.9MB)
테스트 5 〉 통과 (0.04ms, 72.4MB)
테스트 6 〉 통과 (0.04ms, 72.3MB)
테스트 7 〉 통과 (0.05ms, 74MB)
테스트 8 〉 통과 (0.02ms, 74.6MB)
테스트 9 〉 통과 (0.03ms, 75.8MB)
테스트 10 〉 통과 (0.03ms, 75.9MB)
테스트 11 〉 통과 (0.05ms, 84.3MB)
테스트 12 〉 통과 (0.03ms, 76MB)
테스트 13 〉 통과 (0.03ms, 72.3MB)
테스트 14 〉 통과 (2.79ms, 73.4MB)
테스트 15 〉 통과 (3.52ms, 75.2MB)
테스트 16 〉 통과 (9.20ms, 81.7MB)
테스트 17 〉 통과 (10.82ms, 85.5MB)
테스트 18 〉 통과 (13.37ms, 75.5MB)
테스트 19 〉 통과 (11.95ms, 82.9MB)
테스트 20 〉 통과 (10.79ms, 83.7MB)
효율성 테스트
테스트 1 〉 통과 (0.12ms, 55.7MB)
테스트 2 〉 통과 (0.11ms, 56.2MB)
테스트 3 〉 통과 (530.73ms, 180MB)
테스트 4 〉 통과 (825.77ms, 215MB)
채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0
다른사람의 풀이
class Solution {
public boolean solution(String[] phoneBook) {
Arrays.sort(phoneBook);
boolean result = true;
for (int i=0; i<phoneBook.length-1; i++) {
if (phoneBook[i+1].startsWith(phoneBook[i])) {
result = false;
break;
}
}
return result;
}
}
채점을 시작합니다.
정확성 테스트
테스트 1 〉 통과 (0.21ms, 81.1MB)
테스트 2 〉 통과 (0.17ms, 72.9MB)
테스트 3 〉 통과 (0.19ms, 73MB)
테스트 4 〉 통과 (0.18ms, 74.8MB)
테스트 5 〉 통과 (0.20ms, 75.6MB)
테스트 6 〉 통과 (0.19ms, 75.5MB)
테스트 7 〉 통과 (0.21ms, 72.1MB)
테스트 8 〉 통과 (0.17ms, 77MB)
테스트 9 〉 통과 (0.17ms, 75.9MB)
테스트 10 〉 통과 (0.19ms, 72.5MB)
테스트 11 〉 통과 (0.21ms, 71.8MB)
테스트 12 〉 통과 (0.22ms, 79.8MB)
테스트 13 〉 통과 (0.17ms, 76.7MB)
테스트 14 〉 통과 (1.80ms, 73.7MB)
테스트 15 〉 통과 (2.16ms, 79.1MB)
테스트 16 〉 통과 (2.41ms, 76.1MB)
테스트 17 〉 통과 (2.73ms, 75.3MB)
테스트 18 〉 통과 (3.47ms, 74.1MB)
테스트 19 〉 통과 (3.51ms, 78.5MB)
테스트 20 〉 통과 (4.25ms, 74.9MB)
효율성 테스트
테스트 1 〉 통과 (19.67ms, 56MB)
테스트 2 〉 통과 (16.61ms, 59.5MB)
테스트 3 〉 통과 (332.50ms, 98.4MB)
테스트 4 〉 통과 (297.48ms, 96.4MB)
채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0
3. 위장
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return
입출력
- 입력 : [의상의 이름, 의상의 종류] 의 배열
- 출력 : 서로 다른 옷의 조합의 수
제한사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_’ 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.