[Programmers/JAVA] 전화번호 목록 / 프로그래머스 코딩 테스트 연습

전화번호 목록

 

---

문제 설명

 

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

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

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

---

예시

 

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

---

코드 해석 및 전체 코드

Hash 사용하여 문자열 포함하고 있는지 구하기

1. HashSet 선언하고 phone_book 초깃값으로 넣기

2. 이중 for문을 반복하는데, 바깥쪽 for문은 배열 길이만큼 반복

3. 안쪽 for문은 phone_book[i] 길이만큼 반복

4-1. 0부터 문자열길이만큼 반복할때마다 문자열을 쪼개서 해시에 포함하고 있는지 찾기

4-2. 포함할 경우 해당 문자열을 접두사로 사용한 전화번호가 있는 것이므로 false 반환

 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Set<String> p = new HashSet<String>(Arrays.asList(phone_book));

        for (int i = 0; i < p.size(); i++) {
            for (int j = 0; j < phone_book[i].length(); j++) {
                if (p.contains(phone_book[i].substring(0, j)))
                    return false;
            }
        }
        return answer;
    }
}

점수가 짜서 조금 슬픔. ㅠㅠ

---

정렬 방식

주제가 해시이지만 처음 접근은 정렬로 시작했다. 

배열 형태가 String이지만 정렬 메소드를 사용하여 정렬 후 시도했었는데, substring을 사용하는데 런타임이 발생하였다.

그래서 정렬 상태를 확인하니 원하는 방식대로 정렬되지 않은 것을 확인할 수 있었다. 

내가 원하는 방식은 길이순으로 정렬된거였는데, 생각해보니 정렬은 123 순서대로 되는거라 애초에 생각과는 다른 요청을 보낸 것이었다.

그래서 내가 제일 많이 사용하는... 버블 정렬을 사용하여 정렬해보았는데, 효율성에서만 시간 초과가 나고 정확성은 모두 통과하였다. 퀵정렬을 사용하면 통과되려나 생각하긴 했으나 주제가 해시인 이유가 있겠거니 해 방향을 틀었다. 

import java.util.Arrays;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        for(int i = 0; i < phone_book.length; i++){
            for(int j = 0; j < phone_book.length -1 - i; j++){
                if(phone_book[j].length() > phone_book[j+1].length()){
                    String temp = phone_book[j];
                    phone_book[j] = phone_book[j+1];
                    phone_book[j+1] = temp;
                }
            }
        }
        
        // 마지막 전화번호와 겹치는 접두어는 없음
        for(int i = 0; i < phone_book.length - 1; i++){
            //System.out.println(phone_book[i]);
            int length = phone_book[i].length();
            for(int j = i+1; j < phone_book.length; j++){ 
                String p = phone_book[j].substring(0, length);
                if(phone_book[i].equals(p)) return false;
            }
        }
        return answer;
    }
}

테스트 1에서 0.17초 나와서 효율성을 내심 기대함

---

주제가 해시이지만 다양한 방식으로 풀 수 있는 문제라 생각된다.

그래서 그런지 다른 사람의 코드에 태클을 거는 사람이 꽤 많이 보인다.

나와 다른 방식으로 짠 코드를 보면서 서로 배워갔으면 좋겠다.

이렇게 다양한 방식으로 풀 수 있는 코드를 보면 생각의 차이에 따라 각기다른 코드가 나올 수 있다는 걸 새삼 깨달았다.

 

github

programmers