[프로그래머스] #23 전화번호 목록(java)

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

 

 

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_bookreturn

["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

코드1

import java.util.* ;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        for(int i =0; i<phone_book.length; i++){
        phone_book[i].replaceAll(" ","");
        }
        for(int i =0; i<phone_book.length-1; i++){
            for(int j=i+1; j<phone_book.length; j++){
            if(phone_book[j].startsWith(phone_book[i])){
                return false;
            }
                else{
                    answer = true;
                }
        }
        }
        return answer;
    }
}

결과

정확성: 83.3

효율성: 8.3

합계: 91.7 / 100.0

 

풀이1

음.. 우선 처음에 단순 배열로 문제를 풀었는데 저것도 한번에 풀진 못했다.ㅠ

문제를 잘 읽어보면 "접두사" 인 경우를 구하는건데 단순 포함되는 경우만 생각해서 계속 실패했다.

접두사라는걸 유의해서 sort한 후 startsWith를 사용해서 풀었으나

효율성이 안나와서 통과하지 못했다.

 

코드2

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        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;
    }
}

풀이2

이 경우도 풀이1과 같은 아이디어인데, 

문자열을 sort했기 때문에 1, 11, 2 .. 이런 순서로 정렬된다는 것을 생각해서 i와 바로 다음 i+1번째만 비교하면 된다는

차이점이 있다. 이중loop가 아니기 때문에 효율성도 합격이다.

 

이처럼 알고리즘을 풀 때 문자열을 계속 계속 비교하는 작업이 필요하다면? 해시를 떠올리는게 좋다고 한다! 해시문제이기도 하고 그래서 해시를 이용했다. 

 

 

코드3

import java.util.* ;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        HashMap<Integer,String> hm = new HashMap<Integer,String>();
        for(int i=0; i<phone_book.length; i++){
        hm.put(i, phone_book[i]); }
        for (int i=0; i<phone_book.length-1;i++){
            
            if(hm.get(i+1).startsWith(hm.get(i))){
                return false;
            }
        }
        return answer;
    }
}

풀이3

3번 로직을 그대로 해시로만 구현했다. 문제를 읽고 해시로 푸는걸 떠올리도록 연습하는게 필요할 것 같다.