[프로그래머스] 전화번호 목록 (해시 Lv. 2) - 자바 Java

0. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3) 
• Youtube 영상으로 설명을 보고 싶으시다면 다음 영상을 참고하세요.
  

  

1. 문제 설명 (출처 : 프로그래머스, 원 출처)

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

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

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• N개의 전화번호가 들어오면, 이중 한 전화번호가 다른 전화번호의 접두어(?)인지를 확인하는 것이다.
• 즉, 아무 한 전화번호가 다른 전화번호의 시작부터의 일부와 동일하면 false
• 서로 연관이 없으면 true를 return 한다

간단한 예시로 시작한다.

• phone_book[0]이 phone_book[2] ('1이라는 값')으로 시작하기 때문에 false를 return 하는 것이 기댓값이다.
• 컴퓨터에게 이 동일한 업무를 시키는 방법은 크게는 2가지, 작게는 3가지라고 생각하여 정리했다.

 

1. 해결책 1 : 2중 Loop을 통해 서로가 서로의 접두어인지를 전부 확인하는 방법
2. 해결책 2 : 해시를 통해 접두어가 존재하는지를 확인하는 방법

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3-1. 해결책 1 - Sort/Loop을 사용한 solution

• 명색이 해시 문제라 해시로 풀어야 한다는 걸 알지만, 시험에서는 유형을 정해주지 않는다는 함정이 있다.
• 시험 상황에서 2중 Loop 외에는 해답이 떠오르지 않았다면 시도해보지 않고 다른 해결책을 찾았을 것이다.
• 하지만 블로그는 내용을 공부/정리/공유하기 위함이니 2중 Loop solution을 간단하게 정리해보자.

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phoneBook) {
        // 1. phoneBook을 sorting한다.
        Arrays.sort(phoneBook);

        // 2. 1중 Loop을 돌며 앞 번호가 뒷 번호의 접두어인지 확인한다.
        for (int i = 0; i < phoneBook.length - 1; i++)
            if (phoneBook[i + 1].startsWith(phoneBook[i]))
                return false;
        
        // 3. 여기까지 오면 접두어가 없다는 것이다.
        return true;
    }
}

1) 2중 Loop을 사용한 상호 비교

• 가장 간단한 방법으로 모든 전화번호를 서로와 비교하는 것이다.
• 간단 예시처럼 총 3개가 있는 경우 0 vs 1 / 0 vs 2 / 1 vs 2 의 순서로 index i와 j가 정의된다.
• 정렬을 해놓으면 다음과 같이 나온다.

index i와 i위치의 값, j와 j위치의 값을 서로 비교한다

• 이렇게 수행하다보면 i==0 / j==2일 때 1이 12의 접두어이기 때문에 false를 return 하게 된다.
• String1.startsWith(String2)
  • String1이 String2로 시작되는지 (접두어인지)를 찾아주는 String Class의 함수이고, 이 문제에서 사용하기 아주 적합한 함수이다.
  • 필자도 C와 C++을 기반으로 프로그래밍에 입문한 터라 Java의 Library라는 개념이 낯설고, 때로는 너무 날로 먹는(?) 기분이 들기도 한다.
  • 하지만 좋은 것을 아는 만큼 내 퇴근 시간이 단축되고, ms 혹은 us 단위의 성능을 따지지 않는 대부분의 업계에서는 Library를 활용하여 가독성을 높이는 게 원활한 실무를 위해 훨씬 중요하게 여겨진다.
• phone_book[i]가 phone_book[j]로 시작하는지, 반대로 phone_book[j]가 phone_book[i]로 시작하는지 양쪽을 다 확인하여 둘 다 없으면 i/j의 index 값을 바꿔가며 전부 비교하면 된다.
• 혹시 i/j가 늘어나는 순서가 헷갈린다면 손코딩을 강력하게 추천한다. 특히 초반에는 CPU가 동작하는 방식을 한 단계씩 완전히 모사해보는 연습이 단순한 구현 버그와 디버깅 시간을 단축시켜 훨씬 빠르고 효율적인 프로그래머가 되게 해주는 것 같다..
• 결국엔 손이 느린게 문제가 아니라 머리가 느린 게 문제라서 그런 것 같다. 

 

3-2. Hash를 사용한 solution

• 그래도 Hash 문제이고 개념을 이해하는 것이 중요하니 동일한 문제를 Hash로 풀어보자.
• phoneBook의 모든 번호를 Hashing 해두고 나서 접두어 찾는 방식으로 풀어보면 다음 코드가 나온다.

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);
        
        // 3. 모든 전화번호의 substring이 HashMap에 존재하는지 확인한다.
        for (int i = 0; i < phoneBook.length; i++)
            for (int j = 0; j < phoneBook[i].length(); j++)
                if (map.containsKey(phoneBook[i].substring(0, j)))
                    return false;

        return true;
    }
}

1) HashMap 만들기

• HashMap이란 Key-Value의 Pair를 관리하는 클래스이다.
• HashMap<String, Integer>로 지정하면 Key는 String 형태, Value는 Integer 형태로 정의하는 것이다.
• 이 문제에서 Key는 전화번호로 설정하여 전화번호의 존재 유무를 Contains 기반으로 확인한다.
• Key만 갖고도 존재유무를 판단할 수 있어서 value는 큰 의미 없다.

2) 모든 전화번호 Hashing 하기 (Hash Map에 추가하기)

• 'Hashing을 한다'라고도 표현하는데, HashMap에 전화번호를 전부 추가해보자. 
• 위 코드의 동작 방식은 다음 예시로 설명하는 것이 가장 쉽게 이해가 가능할 것이다.
• Index 0

0번 Index의 전화번호인 12를 Hashing 한다

• Index 1

1번 Index의 전화번호인 345를 Hashing 한다

• Index 2

2번 Index의 전화번호인 1을 Hashing 한다

• Hash Map을 보고 나면 별게 아니다. 이 문제에서는 Key 값으로 전화 번호를 관리하는 전화번호부 같은 것이다.
• HashMap.put(Key, Value) : Hash Map에 Key와 Value를 한 쌍으로 입력하는 함수이다.

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

• 존재하는 모든 전화번호가 HashMap에 등록되었다.
• 이제는 각 전화번호의 접두어가 HashMap에 존재하는지 확인하는 것이다.
• Length 1~전체 길이 - 1 까지의 substring을 떼어서, HashMap에 존재한다면, 접두어가 존재한다고 확인할 수 있다.
• 간단 예시에서는 "12"의 substring인 "1"을 추출한다.
• HashMap.containsKey(String)
  • String이라는 Key가 현재 HashMap에 존재하는지 확인하는 함수이다.
  • 이 함수를 통해 현재까지 HashMap에 등록된 Key가 있는지 확인할 수 있고, 현 문제에서는 접두어가 HashMap에 존재하는지 확인할 수 있다.

 

4. 참 쉽죠?

• Hash를 사용해서 문제를 풀 수 있는 방식은 무궁무진하다. 필자도 다른 방식을 먼저 생각해서 풀었는데, 어찌 됐든 정확한 해답을 얻는 빠른 코드라면 전부 좋다.
• 프로그래머스 플랫폼이 정말 좋은 이유는 타 플랫폼 대비 서로의 코드를 보고 배우기 매우 용이하게 되어있다는 점이다. 다른 사람의 코드를 무단 복사나 도용하는 것은 틀린 행위지만, 잘 짜여진 코드를 보는 것만큼 좋은 공부법도 없어 보인다.
• 잘 짜여진 코드는 직관적이고 읽기도 편해서, 이런 코드는 보다 보면 이 사람이 어떤 생각으로 문제를 접근했는지 까지도 보이게 된다. 꼭 문제를 본인만의 방식으로 해결한 뒤에 더 뛰어난 사람들의 코드를 보면서 배우는 시간을 가지면 좋을 것 같다.

 

5. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3)  
• Youtube 영상으로 설명을 보고 싶으시다면 다음 영상을 참고하세요.