https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=java
전화번호가 다른 전화번호의 시작번호라면 -> false 반환
없으면 true 반환
자바에서 문자열 처리 시 phone_book[i+1][j]
이렇게 접근할 수 없고, String에서 특정 문자에 접근하려면 charAt()
메서드를 사용한다.
이때, 문제처럼 문자열의 접두어
인지 아닌 지 확인하려면 startsWith()
메서드가 더 효율적임.
1차 시도: CharAt() 사용 (정답)
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
// 1. 정렬
Arrays.sort(phone_book);
// 2. for문 순회하면서 접두어 탐색
for (int i=0; i<phone_book.length -1; i++){
String cur = phone_book[i];
String nxt = phone_book[i+1];
// 만약 다음 문자열이 더 짧다면 접두어 불가
if(nxt.length() < cur.length()){
continue;
}
// charAt()으로 문자열 인덱스 비교
boolean answer = true;
for(int j=0; j<cur.length(); j++){
if(cur.charAt(j) != nxt.charAt(j)){
answer = false;
break;
}
}
if(answer){
return false;
}
}
return true; // 접두어 아니라면 true 반환
}
}
2차 시도: startsWith() 사용 (정답)
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
// 1. 오름차순 정렬
Arrays.sort(phone_book);
for(int i=0; i<phone_book.length -1; i++){
if(phone_book[i+1].startsWith(phone_book[i]))
return false;
}
return answer;
}
}
3차 시도: HashMap 사용 (정답)
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
// HashMap 사용
HashMap<String, Integer> map = new HashMap<>();
// 1.전화번호부 만들기
for(int i=0; i<phone_book.length; i++){
map.put(phone_book[i], 1);
}
// 2.현재 전화번호의 접두어가 map 에 있는지 체크.
for(int i=0; i<phone_book.length; i++){
// 접두어의 길이 결정
for(int j=1; j<phone_book[i].length(); j++){
// 전화번호에서 접두어가 포함되는지 체크: substring
if(map.containsKey(phone_book[i].substring(0,j))){
return false;
}
}
}
return answer;
}
}
문제풀이