문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제
phone_book return
["119", "97674223", "1195524421"] false
["123","456","789"] true
["12","123","1235","567","88"] false
입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.
풀이과정
처음 풀이는 사실 JAVA가 아니라 C++로 하였다. substring을 이용하여 풀이를 하였으나 결국엔 틀렸으니 C++코드는 추후 다루도록 해볼게요.
자바에서 처음 짠 코드는 substring을 이용한 이중 for문 구조였습니다.
맨 처음 코드
class Solution {
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
int len = phone_book.length();
for(int i = 0;i<len - 1;i++){
for(int j = i;j<len;j++){
if(phone_book[i].substring(0,2).eqals(phone_book[j].substring(0,2)){
boolean answer = false;
return answer;
}
else{
boolean answer = true;
return answer;
}
}
}
}
}이 코드에서 처음 오류가 발생한 부분은 return answer부분이었어요.
자바는 모든 경우에서의 반환값이 있어야하기 때문에 answer 선언을 밖으로 빼주고 코드 맨 마지막에 return을 했습니다.
첫번째 수정
class Solution {
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
int len = phone_book.length();
boolean answer = true;
loop:
for(int i = 0;i<len - 1;i++){
for(int j = i;j<len;j++){
if(phone_book[i].substring(0,2).eqals(phone_book[j].substring(0,2)){
answer = false;
break loop;
}
else{
answer = true;
}
}
}
return answer;
}
}여기서 false가 나왔을 때 바로 break를 해주기 위해 이중 for문 위에 loop:를 붙여준 후 break loop;를 하여 loop가 붙은 for문을 바로 탈출하게 해주었어요.
이 코드는 시간이 많이 걸리고 효율이 좋지 않은 코드일 뿐더러 정답률이 54%가량 밖에 나오지 않았습니다.
그래서 다시 수정하기로 했습니다.
가장 첫번째 문제는 정렬을 했음에도 불구하고 n^2의 성능을 가지고 있다는 점, 정렬을 했음에도 값을 모두 비교하고 있었던 점이었어요.
그리고 친구(?)를 통해 자바에는 startsWith()와 endsWith()라는 좋은 함수가 있다는 것을 배웠습니다... 나의 헛고생..
두번째 수정이
import java.util.Arrays;
class Solution {
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
int len = phone_book.length;
boolean answer = true;
for(int i = 0;i<len - 1;i++){
String str1 = new String(phone_book[i].substring(0,2));
String str2 = new String(phone_book[i+1].substring(0,2));
if(str1.startsWith(str2)) {
answer = false;
break;
}
}
return answer;
}
}갑자기 엄청나게 간결한 코드가 나왔죠. 여기서 예제는 모두 통과!!
하지만 제출 후 채점은 처참히 54%.. 런타임 에러가 계속해서 떴죠.
startWith()를 쓸 때 접두어를 정확히 하기위해선 앞 두 글자를 비교해줘야겠다! 라는 생각에 substring을 사용했는데 여기서 큰 문제가 발생합니다.
똑똑한 사람들은 눈치 채셨겠지만 제한 사항을 보시면 최소가 1입니다. 두번째 글자가 없을 수도 있다는 말입니다.
그래서 결국 최최최종 수정을 하였습니다.
최최최종 수정
import java.util.Arrays;
class Solution {
public boolean solution(String[] phone_book) {
Arrays.sort(phone_book);
int len = phone_book.length;
boolean answer = true;
for(int i = 0;i<len - 1;i++){
if(phone_book[i+1].startsWith(phone_book[i])) {
answer = false;
break;
}
}
return answer;
}
}
여기서 if안에 함수를 넣어 boolean 값을 판별하고 answer의 값을 넣어주는 이유는
answer = phone_book[i+1].startsWith(phone_book[i]); 하고 if문에서 answer를 판단할 경우
answer = phone_book[i+1].startsWith(phone_book[i]);
if(answer){
answer = false;
break;
}같은 접두어가 있어도 false, 같은 접두어가 없어도 false가 되어 오류가 발생하기 때문입니다.
만약 변수에 넣어 비교를 하고 싶다면 새로운 boolean값을 선언해야 합니다.
아직 자바의 함수 startsWith()와 endsWith()는 익숙하지 않아 이 개념은 따로 올려보도록 할게요.