[프로그래머스 / Level2] 전화번호 목록 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/42577?language=java 

코딩테스트 연습 - 전화번호 목록

 

풀이

[입출력 예제]

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

첫번째 테스트케이스를 예시로 설명해보자. 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하기 위해서는 "119", "97674223", "1195524421" 세 개의 문자열(A)에 대해 각각 if(A가 접두어인 문자열 B가 존재하는가?")의 참/거짓을 반복문으로 체크해야 된다. 단순히 한 요소를 이를 제외한 나머지 요소들과 하나씩 비교하면 될 문제지만 이렇게 하나씩 모두 비교할 경우 불필요하게 처리 시간이 많이 걸리게된다. 처리 시간을 줄이기 위해 '접두어일 수 있는 경우'만 비교 연산을 수행해야 한다.

1. 반복문

아래 코드는 phone_book 배열을 정렬한 뒤, 반복문을 통해 한 요소가 자신의 오른쪽에 위치한 요소의 접두어인지를 확인하고 있다. 문자열 배열은 기본 사전순 정렬된다(숫자 오름차순 -> 문자열 길이 오름차순). 이렇게 정렬된 상태에서 phone_book[i]가 phone_book[i+1]의 접두어면서 phone_book[i+2]의 접두어일 수는 있어도, phone_book[i+1]의 접두어가 아니지만 phone_book[i+2]의 접두어일 수는 없다. 즉 자신의 오른쪽에 인접한 요소랑만 비교를 수행하면 되는 것. (=불필요한 비교 감소)

public boolean solution(String[] phone_book) {
    // 1. 숫자 오름차순 -> 길이 오름차순 정렬
    Arrays.sort(phone_book);

    // 2. 앞 번호가 뒷 번호의 접두어인지 체크
    for (int i = 0; i < phone_book.length - 1; i++) {
        if (phone_book[i + 1].startsWith(phone_book[i]))
            return false;
    }

    // 3. for문 내 if조건에 걸리지 않고 끝남
    return true;
}

 

[String 클래스 메서드]

메서드	설명
boolean startWith(String prefix)	주어진 문자열(prefix)로 시작하는지 검사한다.
boolean endWith(String suffix)	주어진 문자열(suffix)로 끝나는지 검사한다.
boolean contains(CharSequence s)	지정한 문자열(s)이 포함되었는지 검사한다.
int indexOf(String str)	주어진 문자열이 존재하는지 확인하여 그 위치를 알려준다. 없으면 -1을 반환.
int lastIndexOf(String str)	주어진 문자 또는 문자코드를 문자열의 오른쪽 끝에서부터 찾아서 그 위치를 알려준다. 없으면 -1을 반환.

 

2. 해시

for문을 이용해서도 원하는 답을 얻을 수 있지만, 문제 분류가 Hash이기 때문에 HashMap을 사용한 풀이도 알아보자.
문제에서 "같은 전화번호가 중복으로 들어있지 않다."고 조건을 줬기 때문에 중복을 허용하지 않는다는 Key 조건에 부합한다. phone_book 배열의 전화번호를 Key로 하는 HashMap을 생성해준다. 이제 하나의 문자열 A를 대상으로 "A의 접두어가 해시맵에 존재하는가?" 를 체크해주면된다. 이 때 주의할 것은 '접두어'를 찾는 것이 때문에 (문자열의 0번째 문자 ~ 마지막에서 두번째 문자) 까지만 접두어로 뽑아내 비교해야 한다.

예를 들어 테스트케이스가 ["119", "1", "234"] 이고, "문자열A의 접두어가 존재하는가?"에서 문자열 A가 "119" 일 경우, "119"에서 나올 수 있는 접두어는 "1", "11" 이다. 접두어인 문자열이 존재하는지를 2번 체크해야 되는 것이다. 물론 HashMap에 "1"이 존재하기 때문에 첫번째 반복에서 false를 반환(=접두어 문자열 존재함)하고 끝나게 된다.

"119"의 접두어	추출 방법	접두어 문자열 존재 여부
"1"	"119".subString(0, 1)   // 0~0 자르기	true
"11"	"119".subString(0, 2)   // 0~1 자르기	false

 

코드

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Integer> map = new HashMap<>();
        // HashMap에 전화번호 문자열 key 저장
        for (String phone_number : phone_book) {
            map.put(phone_number, 1);
        }

        for (String phone_number : phone_book) {
            for (int j = 1; j < phone_number.length(); j++) {
            	// substring(0, 1) ~ substring(0, length-1)
                String prefix = phone_number.substring(0, j);
                if(map.containsKey(prefix))
                    return false;
            }
        }

        return true;
    }
}

 

1. 전화번호 문자열을 Key로 하는 HashMap 생성 (※ HashMap의 Key는 중복 불허)
2. 반복문으로 각 전화번호의 접두사가 HashMap에 존재하는지 확인
3. 각 전화번호의 접두사는 (문자열길이 - 1)개 만큼 존재하며, 이 접두사를 하나씩 확인해야 함
   *접두사 : substring(0, 1) ~ substring(0, length-1)
4. 전화번호에서 추출해낸 접두사가 HashMap에 존재하면 false 반환
5. 아무 접두사도 HashMap에 존재하지 않아 if문에 걸리지 않고 반복문이 끝났으면 true반환