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

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

컬렉션 함수를 잘 이용하면 간단히 풀릴 문제였는데 적절한 사용을 못하고 슬라이딩 윈도우로 풀다가 인덱스바운더리 에러만 맛봤다... 가슴이 아파서 정리해둔다

내가 참 간과한 것이 있는데, String 배열도 배열이라 Arrays.sort() 가 사용가능 하다는 점, 그리고 사전순서대로 정렬이 된다는 점이다.
대체 왜 막연히 길이가 짧은 순서대로 정렬이 된다고 생각했던 걸까... 아래와 같이 시험해보니 길이가 긴 문자열이라도 사전순으로 앞이면 앞에 정렬된다.

String[] s = {"119", "97674223", "1195524421", "11111111111111111111111111"};
for (String s1 : s) {
    System.out.println(s1);
}
Arrays.sort(s);
System.out.println();
for (String s1 : s) {
    System.out.println(s1);
}

// 출력결과
119
97674223
1195524421
11111111111111111111111111

11111111111111111111111111
119
1195524421
97674223

 

Arrays.sort() + for문 풀이

이 코드에서 포인트는 String.startsWith() 함수다. 이런 함수가 있다는 사실조차 까먹고 있었다...
이 함수를 사용하면 i와 i+1번째 문자열 중에 어떤것이 더 긴지에 대한 고려를 할 필요도 없다. (함수가 알아서 해주니까...)

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);

        for (int i = 0; i < phoneBook.length - 1; i++)
            if (phoneBook[i + 1].startsWith(phoneBook[i]))
                return false;
        
        return true;
    }
}

성공은 하는데 좀 느린감이 있다.

 

HashMap 사용 풀이

해쉬맵 가지고 정말 별의 별짓을 다해봤는데... containsKey() 함수가 포인트다.
정렬할 필요 없이, 문자열 마다 substring(0,j) 씩 부분 문자열을 추출해 containsKey() 로 검색하면 빠르게 해결할 수 있다.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phoneBook) {
        HashMap<String, Integer> hp = new HashMap<>();
        for (String s : phoneBook) {
            hp.put(s, hp.getOrDefault(s, 0) + 1);
        }
        for (int i = 0; i < phoneBook.length; i++) {
            for (int j = 0; j < phoneBook[i].length(); j++) {
                if (hp.containsKey(phoneBook[i].substring(0, j))) {
                    return false;
                }
            }
        }

        return true;
    }
}

확실히 정렬+for문 보다 성능이 좋다.