프로그래머스/Java) 전화번호 목록

핑크퐁 123 숫자놀이

문제 설명

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

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

 

 

문제 풀이

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public boolean solution(String[] phoneBook) {
//        1. HashMap 선언
        Map<String, Integer> map = new HashMap<>();
 
//        2. 모든 전화번호를 HashMap에 추가한다.
        for (int i = 0; i < phoneBook.length; i++) {
            map.put(phoneBook[i], i);
        } // 여기서 Value 값이 되는 i int 값은 무의미하다. (Key만 이용해서 해결할 예정이므로)
 
//        3. 모든 전화번호의 substring이 HashMap에 존재하는지 확인한다.
        for (int j = 0; j < phoneBook.length; j++) {
            for (int k = 0; k < phoneBook[j].length(); k++) {
                if (map.containsKey(phoneBook[j].substring(0,k))) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

1. HashMap

HashMap이란 Key:Value 쌍을 이루는 집합을 관리하는 클래스이다.

코드 7번째 줄에서 <String, Integer>로 타입을 지정했는데 이는 Key = String, Value = Integer 타입으로 정의하는 것이다.

위 문제를 풀이하기 위해 Key에 해당하는 값을 전화번호로 지정하였고

임의 Key값의 존재유무를 Contains를 통해 확인했다.

 

 

 

2. 전화번호 Hashing (HashMap에 추가)

HashMap에 값을 추가하는 것을 Hashing이라고도 표현한다.

 

입력된 전화번호(예제 3) {"12","123","1235","567","88"} 

위와 같은 숫자배열이 입력되었다는 가정 하에 풀이를 이어가보려고 한다.

첫번째 for문을 돌며 전화번호를 Hashing하면 아래 표와 같은 HashMap이 만들어진다.

Key	Value
12	0
123	1
1235	2
567	3
88	4

 

0부터 '배열의 길이'까지 반복문이 실행되면서 key 값으로 전화번호 배열의 순서에 맞춰 1개씩 Hashing.

Value 값은 반복문이 돌아간 횟수를 카운팅하듯 부여된다.

풀이에 Value값은 쓰이지 않을 예정이므로 임의의 값을 넣었다고 생각하면 쉽다.

이 문제를 풀기 위해 사용한 HashMap은 그저 '전화번호부'인것이다.

 

 

 

3. 각 전화번호의 접두어가 HashMap에 존재하는지 확인

주어진 전화번호 배열이 모두 Hashing 되었고 이제 문제의 조건에 따라 확인하는 일만 남았다.

 

String substring을 이용하여 각 전화번호의 첫번째 ~ (마지막 - 1) 글자를 떼어, HashMap Key값들과 비교해보면

접두어 존재여부를 알 수 있게된다.

String substring(int index)에 대한 자세한 설명

 

"1235"를 예로 들어 substring을 간단히 설명해보자면 다음과 같다

public class Main {
    public static void main(String[] args) {
        String str = "1235";
        System.out.println(str.substring(0,2));
        System.out.println(str.substring(0,3));
    }
}
 

이후 떼어낸 문자열을 Contains를 이용하여 HashMap에 존재하는지 탐색한다.

접두어가 HashMap에 존재하므로 문제에 제시된 조건에 따라 false를 반환하게 된다.

 

문제에서 접두어가 존재한다면 false를 출력하도록 되어있으니 전부 탐색할 필요 없이 반복문을 돌다가

접두어를 발견하게되면 즉시 false를 반환하고 종료한다.

그렇지 않고 반복문을 모두 돌았지만 if문에서 걸리지 않은경우 true를 반환하면 된다.

 

 

이렇게 또 한 문제 해결 완!

 

어우 어려워..

 

출처

프로그래머스 전화번호 목록 : https://school.programmers.co.kr/learn/courses/30/lessons/42577

핑크퐁 123 숫자놀이 : 구글플레이스토어

문제 풀이 참고 : 개발자로 취직하기.Tistory