[PGS] 전화번호 목록 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.*;

public class Solution {

	// 반복문 풀이
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i+1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
    
    // 해시 풀이
    public boolean solution(String[] phoneBook) {
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < phoneBook.length; i++) 
            map.put(phoneBook[i], i);
        
        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;
    }
}

📄 해설

두 방법 모두 접근에만 성공하고, 이를 코드로 옮기기만 하면 된다.
코드로 옮기기 쉬운 난이도의 문제이므로, 천천히 고민하며 손으로 써본다면 쉽게 해결 가능

접근(반복문)

• 해시 문제로 분류되어 있어, 해시로 접근하려 했으나, 반복문으로 풀려서 반복문 풀이와 해시 풀이를 함께 업로드 하였음
• 한 문자열이 다른 문자열의 접두어가 되기 위해서는 해당 문자열이 짧아야함
• 배열을 정렬해주고, 바로 다음 문자열의 접두어인지를 확인한다.
• 바로 다음 문자열만 비교하는 이유?
  • 바로 다음 문자열의 접두어가 아닌데, 이후 문자열의 접두어일리가 없음.

과정(반복문)

• 접두어 비교에는 startsWith() 메소드를 활용한다.
• 이외에는 접근과 동일함

접근(해시)

• HashMap<String, Integer> 을 만들고, 각 전화번호의 접두어가 HashMap 의 key 로 존재하는지 확인한다.

과정(해시)

• 접두어 비교에는 containsKey() 메소드를 활용한다.
• 역시 접근과 동일함