[programmers / 프로그래머스 - JAVA] 전화번호 목록 (해시)

문제

---

문제 설명

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

• 구조대 : 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입니다.

내 풀이

---

1st try

class Solution {
    public boolean solution(String[] phone_book) {
        for (int i = 0; i < phone_book.length; i++)
        {
            for (int j = i + 1; j < phone_book.length; j++)
            {
                if ((phone_book[i].length() < phone_book[j].length()))
                {
                    if (phone_book[i].compareTo(phone_book[j].substring(0, phone_book[i].length())) == 0)
                        return false;
                }
                else
                {
                    if (phone_book[j].compareTo(phone_book[i].substring(0, phone_book[j].length())) == 0)
                        return false;
                }
            }
        }
        return true;
    }
}

정말 오랜만에 하는 JAVA이다.

 

처음에 보고 접두사 구하는 거니까 그냥 substring해서

 

비교한 뒤에 리턴하면 되지 않을까 생각했고

 

그에 따라 코드 작성했는데 결괏값이 원하지 않는 게 나와서

 

sysout 찍어 봤더니 ==으로는 비교가 안 됐다.

 

compareTo 생각나서 사용하니 잘 됐고, 채점해 보니 몇 문제 터지길래

 

확인해 봤더니 length 비교 후 조건 다르게 지정해야 했다.

 

정확성 테스트 통과했지만 효율성은 두 개 터져서 다시 짜야 할 듯

 

---

2nd try

class Solution {
    public boolean solution(String[] phone_book) {
        
        String tmp;
        
        for (int i = phone_book.length - 1; i > 0; i--)
        {
            for (int j = 0; j < i; j++)
            {
                   if (phone_book[i].compareTo(phone_book[j]) < 0)
                   {
                       tmp = phone_book[j];
                       phone_book[j] = phone_book[i];
                       phone_book[i] = tmp;
                   }
            }
        }
        
        for (int i = 0; i < phone_book.length - 1; i++)
        {
            if (phone_book[i].length() < phone_book[i + 1].length())
                if (phone_book[i].compareTo(phone_book[i + 1].substring(0, phone_book[i].length())) == 0)
                    return false;
        }
        return true;
    }
}

사전 순으로 정렬하면 i 일 때 i + 1만 확인하면 된다는 방법을 이용해서 해결하려 했다.

 

저번에 공부하다 주워들은 버블 정렬인가 몬가가 기억나서 구현해 봤는데

 

저게 버블 정렬인지는 모르겠고, 정렬 후 비교해 봤다.

 

제출 후 채점 결과 확인하니  정확성 테스트 통과했지만 효율성은 전부 다 터졌다??????

 

개선은커녕 오히려 퇴보했다;;;

 

---

3rd try

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        
        String tmp;
        
        Arrays.sort(phone_book);
        
        for (int i = 0; i < phone_book.length - 1; i++)
        {
            if (phone_book[i].length() < phone_book[i + 1].length())
                if (phone_book[i].compareTo(phone_book[i + 1].substring(0, phone_book[i].length())) == 0)
                    return false;
        }
        return true;
    }
}

예전에 백준 문제 풀 때 Arrays.sort 사용했었는데 아마 그때 퀵 소트 사용한다고 했던 게

 

기억나서 import 후 Arrays.sort 해봤더니 무난하게 테스트 통과했다.

 

++ 찾아보니 듀얼 피봇 퀵소트라고 한다.