처음에 이 문제를 어떻게 풀어야할지 감이 안왔다.
phone_book에서 2개의 원소(a,b라고 가정)를 고르는 2중 for문에, 한 번 더 문자열(b)의 길이만큼 반복하면서 잘라낸 문자열이 가장 바깥 문자열과 일치하는지 검사하는 코드를 슈도코드로 짜봤는데,,
이렇게하면 시간복잡도가 무려 10^12로 너무 컸다..
(대충 제일 바깥 for문의 값이 두번째 for문 값의 접두사인지 확인한다는 로직)
(근데 한 번의 반복문으로 짤 수 있는 방법이 있다. 가장 아래에서 소개하겠다)
이 문제는 사실 해시의 카테고리를 타고 들어간거인데, 해시를 어떻게 사용해야하지?싶었다.
내가 생각하지 못했던 것은 2가지다.
- 전화번호를 해시맵의 키로 넣어서 사용한다. (사실 해시의 값은 별 의미가 없다)
- 비교하는 값을 고정하는게 아니라, 반대로(?) 접두사를 만들어서 이 값을 고정하고, 전체를 대상으로 해당 값이 있는지 확인한다.
-> 반대로도 생각할 줄 알기!
Troubleshooting
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
Map<String, Integer> map = new HashMap<>();
for(int i=0; i<phone_book.length; i++) {
map.put(phone_book[i], i);
}
for(int i=0; i<phone_book.length; i++) {
for(int j=1; j<phone_book[i].length(); j++) {
if(map.containsKey(phone_book[i].substring(0,j+1))) {
return false;
}
}
}
return true;
}
}문제
이 경우에도 false가 나온다 (답은 true)
원인
substring()의 두번째 파라미터는 끝 인덱스이다. 들어오는 값의 -1 까지하기때문에, 문자열 끝까지 다 수행해주기위해서 'j+1' 이라고 했는데, 이게 문제다.
이렇게하면 무조건 'phone_book[i].substring(0,j+1)'과 동일한 키 값이 존재할 수 밖에 없다.(문자열 끝까지 자를 경우인 자기자신)
해결
접두사를 만드는 것이기때문에, phone_book[i].substring(0,j) 로 마지막 문자 하나전까지만 해준다.
제출코드
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
Map<String, Integer> map = new HashMap<>();
for(int i=0; i<phone_book.length; i++) {
map.put(phone_book[i], i);
}
for(int i=0; i<phone_book.length; i++) {
for(int j=1; j<phone_book[i].length(); j++) {
if(map.containsKey(phone_book[i].substring(0,j))) {
return false;
}
}
}
return true;
}
}공부한 코드
해시를 사용하지 않고, 일반적인 반복문으로는 어떻게 푸는지 알아보자.
import java.util.Arrays;
class Solution {
public boolean solution(String[] phoneBook) {
// 1. phoneBook을 sorting한다.
Arrays.sort(phoneBook);
// 2. 1중 Loop을 돌며 앞 번호가 뒷 번호의 접두어인지 확인한다.
for (int i = 0; i < phoneBook.length - 1; i++)
if (phoneBook[i + 1].startsWith(phoneBook[i]))
return false;
// 3. 여기까지 오면 접두어가 없다는 것이다.
return true;
}
}한 번의 반복문으로 체크하려면, 정렬이 필수다!
이 부분은 정말 생각하지 못했던 부분이다.
정렬을 하면 사전식으로 정렬되기때문에, 이렇게 되어있을 때에 접두사가 되는 문자열은 무조건 그 다음 문자열의 접두사이다. (그 이후 문자열의 접두사일수도 있는데, 어쨌든 바로 다음 문자열은 무조건이다!)
따라서,
1. 정렬한다
2. startsWith() 라는 아주 간편한 함수를 사용해서 현재 문자열이 다음 문자열의 접두사일 수 있는지 확인한다.
공부한 사항
- HashMap의 containsKey()
- String의 startsWith()
