프로그래머스 전화번호 목록(level 2)
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 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입니다.
이 문제는 해시 카테고리에 있었지만 내가 아직 해시에 익숙하지 않아서인지 해시로 푸는 방법이 떠오르지 않아서 그냥 다른 방법으로 풀었다.
먼저 맨 처음으로 풀었던 코드는
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
String s1 = "";
String s2 = "";
for(int i = 0; i < phone_book.length - 1; i++){
for(int j = i + 1; j < phone_book.length; j++) {
s1 = phone_book[i];
s2 = phone_book[j];
if(s1.length() < s2.length() && s2.contains(s1)) {
answer = false;
break;
}
if(s2.length() < s1.length() && s1.contains(s2)) {
answer = false;
break;
}
}
}
return answer;
}
}
이렇게 .contains() 함수를 사용하여 길이가 짧은 문자열이 긴 문자열에 포함되어 있으면 answer를 false로 바꾸게 하는 코드였는데
테스트케이스 1, 5번에서 실패가 떴다. 한참을 뭐 때문에 뜬건지 생각했는데 contains 함수를 쓰면 접두어가 아닌 경우에도 포함만 되면 false를 내뱉어서 실패가 뜨는 거였다....ㅎ 문제를 잘 기억해야한다...
암튼 그러면 어떻게 하지?했는데 친구가 startsWith 함수를 알려줘서 그것을 이용해서 성공했습니다.
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
String s1 = "";
String s2 = "";
for(int i = 0; i < phone_book.length - 1; i++){
for(int j = i + 1; j < phone_book.length; j++) {
s1 = phone_book[i];
s2 = phone_book[j];
if(s2.startsWith(s1))
return false;
if(s1.startsWith(s2))
return false;
}
}
return answer;
}
}
완료. 근데 사실 한번에 통과한건 아니고
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
String s1 = "";
String s2 = "";
for(int i = 0; i < phone_book.length - 1; i++){
for(int j = i + 1; j < phone_book.length; j++) {
s1 = phone_book[i];
s2 = phone_book[j];
if(s1.length() < s2.length() && s2.startsWith(s1)) {
answer = false;
break;
}
if(s2.length() < s1.length() && s1.startsWith(s2)) {
answer = false;
break;
}
}
}
return answer;
}
}
이렇게 했더니 시간 초과가 떴다. 아마 이중 for문을 써서 시간 효율성이 간당간당한거같다. 언젠간 새로운 코드도 써봐야지...
Author And Source
이 문제에 관하여(프로그래머스 전화번호 목록(level 2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongseolah/프로그래머스-전화번호-목록level-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)