문제
해결 방안 고민
== 전화번호 목록 ==
한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 함
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를
그렇지 않으면 true를 return 하도록 solution 함수를 작성
Markdown
복사
•
문제 이해는 어렵지 않은데 접근법에 대해서 고민을 했던 문제였다.
•
substring을 활용하여 접두어를 찾아서 문제를 해결하는 방향으로 접근하려고 했지만 실패했다.
•
HashMap으로 풀이한 것 이외에 다른 방법으로도 접근해봤다.
◦
startsWith을 활용하여 접두어만 추출해서 비교하는 방식으로 접근했으나 효율성 테스트에서 시간 초과가 발생하였다.
◦
정렬을 활용하여 해결하려고 했으나 정확성 테스트에서 실패하였다(효율성 테스트는 성공).
해결 방법
•
substring과 HashMap을 활용해야 한다. 배열 요소들을 HashMap에 추가한 다음에 HashMap에 있는 키를 substring을 활용하여 포함 여부를 확인하는 방식으로 접근해야 한다.
코드
•
자료구조를 사용하지 않음 (실패)
public class Pro42577 {
public boolean solution(String[] phone_book) {
int length = phone_book[0].length();
int pLength = phone_book.length;
for (int i = 1; i < pLength; i++) {
if (phone_book[i].substring(0, length).equals(phone_book[0])) {
return false;
}
}
return true;
}
}
Java
복사
•
HashMap 활용
import java.util.HashMap;
public class Pro42577 {
public boolean solution(String[] phone_book) {
int length = phone_book.length;
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < length; i++) {
map.put(phone_book[i], i);
}
for (String s : phone_book) {
length = s.length();
for (int j = 0; j < length; j++) {
if (map.containsKey(s.substring(0, j))) {
return false;
}
}
}
return true;
}
}
Java
복사
•
startsWith 활용 - 효율성 테스트에서 시간 초과 발생
public class Pro42577 {
public boolean solution(String[] phone_book) {
int length = phone_book.length;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (phone_book[i].startsWith(phone_book[j])) {
return false;
}
if (phone_book[j].startsWith(phone_book[i])) {
return false;
}
}
}
return true;
}
}
Java
복사
•
정렬을 활용한 풀이 - 효율성 테스트 성공, 정확성 테스트 실패
import java.util.Arrays;
public class Pro42577 {
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
boolean result = true;
int length = phone_book.length;
for (int i = 0; i < length - 1; i++) {
if (phone_book[i + 1].contains(phone_book[i])) {
result = false;
break;
}
}
return result;
}
}
Java
복사
느낀 점
•
substring, HashMap, 정렬, startsWith의 활용법에 대한 내용을 알 수 있었다.
•
접두어가 아닌 접미어를 구하는 경우에도 이와 유사한 로직을 활용하여 접근하면 해결할 수 있을 것이라는 생각이 들었다.