[프로그래머스] (Java) 전화번호 목록 문제 풀이 (해시) - substring, starsWith 메서드

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. 접근방식

2-1. 문제 단순화

 

- 전화번호가 들어있는 배열에서 한 번호가 어떤 번호의 접두어인지 찾는 프로그램 만들기

- 배열 내에서 아무 번호가 같은 배열에 들어 있는 다른 번호로 시작하면 false 리턴

- 서로 관련 있는 번호가 없으면 true 리턴

- 이 때 입출력 예 #1을 보면 접두어인 번호는 바로 옆 인덱스에 붙어 있을 필요가 없음. => 정렬을 해 줘야 함

 

 

2-2. 해결법

 

✅ 이 문제가 해시 문제인 걸 몰랐다면, 어떤 방법으로 풀어도 된다. 가장 먼저 쉽게 떠오르는 방법은 정렬 후 Loop 를 돌려서 i+1번째 인덱스의 값이 i번째 인덱스의 값으로 시작하는 지 확인하는 방법이다.

 

✅ 명색이 해시 문제이니, 해시맵(HashMap) 통해서 확인하는 방법

 

---

3. 문제 풀이 

3-1. Loop

 

- String1.startsWith(String2) 메서드 : String1이 String2로 시작하면 true, 그렇지 않으면 false 반환하는 메서드

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. 배열 정렬하기 - 이 작업을 통해 비슷한 값이 근처에 정렬됨.
        Arrays.sort(phone_book);
        
        // 2. for문(Loop)을 돌면서 뒷 번호가 앞 번호로 시작하는지 확인
        for(int i = 0; i < phone_book.length-1; i++) {
            if (phone_book[i+1].startsWith(phone_book[i])) {
                return false;
            }
        } 
        return true;
    }
}

 

3-2. HashMap

틀린 코드

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. 해시맵 선언
        HashMap<String, Integer> map = new HashMap<>();
        
        // 2.모든 전화번호를 해시맵에 추가
        for (String phone : phone_book) {
            map.put(phone_book[i], 1); // 틀린 코드 1
        }
        
        // 3. 각 번호가 다른 번호의 접두사인지 확인
        for (String phone : phone_book ) {
            for (int i = 1, i < phone_book.length; i++) { // 틀린 코드 2
                if(map.containsKey(phone.substring(0, i))) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

 

틀린 코드 1 : for-each 문에서는 phone_book[i]가 아니라 phone으로 써야 함

틀린 코드 2: phone_book.length가 아니라 i < phone.length()

 

 

 

정답 코드

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. 해시맵 선언
        HashMap<String, Integer> map = new HashMap<>();
        
        // 2. 모든 전화번호를 해시맵에 추가
        for (String phone : phone_book) {
            map.put(phone, 1);
        }
        
        // 3. 각 번호가 다른 번호의 접두사인지 확인
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                if (map.containsKey(phone.substring(0, i))) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

 

✅ map.containsKey()

자바 Map 인터페이스에 정의된 메서드, 해시맵이 특정 키를 포함하고 있는지 확인하는 데 사용된다. 주어진 키가 맵에 존재하는 경우 true, 존재하지 않으면 false를 반환해 준다. (키가 존재하는지만 확인하는 메서드고 키값을 반환하지는 않음.)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 5);

if (map.containsKey("apple")) {
    System.out.println("배열 안에 apple 있어요~");
} else {
    System.out.println("배열 안에 apple 없어요~");
}

 

✅ phone.substring(0, i)

substring(0, i)는 전화번호의 첫 글자부터 i번째 글자 이전까지의 모든 문자를 포함하는 부분 문자열을 반환한다.

 

전화번호가 "12345"라고 가정해 보자, substring(0, i)를 수행하면

• i = 1: phone.substring(0, 1) → "1"
• i = 2: phone.substring(0, 2) → "12"
• i = 3: phone.substring(0, 3) → "123"
• i = 4: phone.substring(0, 4) → "1234"

String phone = "12345";

for (int i = 1; i < phone.length(); i++) {
    String prefix = phone.substring(0, i);
    System.out.println("i = " + i + ", prefix = " + prefix);
}

 

[결과 출력화면]

i = 1, prefix = 1
i = 2, prefix = 12
i = 3, prefix = 123
i = 4, prefix = 1234

 

이렇게 각 i에 대해 phone의 접두사 확인 가능

---

 

4. 동일유형 문제 (해시)

완주하지 못한 선수

[프로그래머스] (Java) 코딩테스트 완주하지 못한선수 문제풀이 🚴‍♂️

 

폰켓몬

[프로그래머스] (Java) 코딩테스트 폰켓몬 문제풀이 🐣