[프로그래머스] 전화번호 목록 : Hash - L2

1. 문제

 

문제 요약

- 어떤 번호가 다른 번호의 접두어인 경우를 구하라

 

처음 시도 때 가장 첫 번째 문자열이 다른 문자열들의 접두어가 되는지 판단하는 줄 알고 접근했다가 계속 오답이 나오길래 꽤 생각했다. 문제를 다시보니 "어떤 번호"가 "다른 번호"의 접두어인지 판단하는 문제였다. 문제 요약하는 습관을 기르자!

 

 

2. 접근

해시 알고리즘으로 분류되어 있어서 해시를 써야될 것 같은데 도저히 풀 방법이 생각나지 않았다.

contains() 함수를 이용해야 될 것 같아서 고민해봤지만 '접두어'인 조건을 어떻게 풀어야할지 몰랐다. contains() 함수를 사용하여, 문자열이 다른 문자열의 포함되는지 알아도 오직 문자열이 시작할 때 포함하고 있어야하기 때문에 어려웠다.

 

결국 못 풀고 다른 사람의 풀이를 보았다. 풀이를 보고 이해한 내용과 알게된 점을 정리 해보겠다.

 

 

3. 다른 사람 풀이

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet();
        for(String arr : phone_book){
            set.add(arr);
        }
        
        for(int i=0; i< phone_book.length; i++){
            for(int j=1; j< phone_book[i].length(); j++){
                if(set.contains(phone_book[i].substring(0,j)))
                    return false;
            }
        }
        return true;
    }
}

 

Set, Set.contains(), String.substring() 을 이용한다.

A = "12";
B = "123456";

 

해당 풀이법은 접두어가 될 문자열을 A, 접두어를 포함할 문자열을 B라고 할 때, 

• 문자열 B를 시작 위치를 기준으로 길이를 1부터 B.length()가 될 때까지 부분 문자열을 생성한다.
• 부분 문자열이 A와 같은지 확인한다. 이때 constains() 함수를 사용한다.
• 만약 true를 반환하면 바로 false를 리턴하여 솔루션을 종료한다.

 

 

4. 알게된 점

set은 contains()

- 객체가 포함되어 있는지 체크

- Map은 containsKey() 또는 containsValue()를 사용할 수 있다.

 

 

startWith 함수

- boolean startWith(String prefix) - java.String

- 대상 문자열이 prefix 문자열로 시작하는지 체크하는 함수이다.

- 여부 확인 후 true/false 값을 리턴

- 문자열로 끝나는지 체크하는 endsWith() 함수로 있다.

	String startsWithT = "자바 코딩 테스트 ";
	System.out.println( startsWithT.startsWith("자바") );  // true