문제 바로가기

접두어 개념

• '첫'문자 시작 '끝'문자 포함X
• 예를들어 119면 접두어는 1,11이다. 19는 접두어가 아니다!

접근방식

처음 문제를 보자마자 자바 스트링 문제에 익숙치 않아서 어떻게 풀면 좋을지 갈피를 못잡았다. 그래서 그냥 바로 구글링했다. 요즘에 보자마자 풀이법이 생각나지 않는 문제는 끙끙 앓기보단 풀이법을 바로바로 찾아보고 내걸로 만드는 편이다.

두가지 풀이가 있다.
1. startsWith사용
2. 해시맵사용

사실 해당 문제는 알고리즘 고득점 Kit에 있는 해시 분류 문제이다. 그런데 gpt한테 물어보니 1번방법이 효율성이 더 좋다고 한다. 두 문제의 풀이를 모두 이해하고 (사실 이번에 startsWith메서드랑 substring메서드 처음 알았다...) 두 방식 모두로 풀어보았다.
사실상 푼 거라기 보단 기존 풀이법을 외우고 다시 쳐보는 느낌으로

첫번째풀이(정렬, startsWith사용)

import java.io.*;
import java.util.*;

class 전화번호목록 {
    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;
    }
}

두번재풀이(HashMap)

import java.io.*;
import java.util.*;

class 전화번호목록2 {
    public boolean solution(String[] phone_book) {
        HashMap<String,Integer> map=new HashMap<>();

        for(int i=0;i<phone_book.length;i++){
            map.put(phone_book[i],i);
        }

        for(int i=0;i<phone_book.length;i++){
            for(int j=0;j<phone_book[i].length();j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
            }
        }
        return true;
    }
}

후기

해시맵 아직 생소하다...
일단 알고리즘 고득점 kit에 있는 해시문제는 모두 풀어보자