[프로그래머스/JAVA] 해시 - 42576번 전화번호 목록

신승현·2022년 12월 27일

Java 복습 프로그래머스

Algorithm Study(백준, 프로그래머스)

목록 보기

65/65

더 좋은 문제 풀이가 있거나 궁금하신 점이 있다면 편하게 댓글 남겨주세요!

📝 문제

전화번호 목록

🤷‍♂️ 접근 방법

String을 활용한 방법1과 HashSet을 활용한 방법2을 비교해보겠습니다.

[String을 사용한 방법1] 메모리: 113 MB, 시간: 346.65 ms
[HashSet을 사용한 방법2] 메모리: 138 MB, 시간: 212.58 ms

위를 통해 HashSet의 성능이 String을 사용한 것보다 좋다는 것을 알 수 있었습니다.
저는 추가적으로 HashMap을 사용한 방식과도 비교를 해보았습니다. 처음에는 HashMap이 value 부분을 추가적으로 사용하여 HashSet 보다 성능이 좋지 않을 것이라고 생각했습니다. 그러나 더 찾아보니 HashSet이 객체 자체를 저장하고 내부적으로 HashMap을 사용하기 때문에 HashMap이 HashSet보다 속도가 더 빠르다는 사실을 알게 되었습니다.
HashMap vs HashSet 비교
참고자료1
참고자료2

다음으로는 문제에 사용된 startsWith() 메소드와 함께 java의 String 관련 함수를 정리해보겠습니다.

📌 String startsWith()

boolean startsWith(String prefix)

java의 String 함수 중 startsWith()는 해당 문자열이 특정 문자열로 시작하는지 확인하는 함수입니다.
해당 문자열로 시작되는지의 여부를 true/false 값으로 반환합니다.
단, 공백도 확인하기 때문에 해당 부분은 주의가 필요합니다.

String str1 = "자바 스프링";
System.out.println(str1.startsWith("자바")); //true

String str2 = " 자바 스프링";
System.out.println(str2.startsWith("자바")); //false

📌 String endsWith()

boolean endsWith(String suffix)

java의 String 함수 중 endsWith()는 해당 문자열이 특정 문자열로 끝나는지 확인하는 함수입니다.
해당 문자열로 반환되는지의 여부를 true/false 값으로 반환합니다.
startsWith() 와 마찬가지로 공백을 확인함으로 주의가 필요합니다.

String str3 = "자바 스프링";
System.out.println(str3.endsWith("스프링")); //true

String str4 = "자바 스프링 ";
System.out.println(str4.endsWith("스프링")); //false

📌 String contains()

startsWith()와 endsWith()와 비슷하게 특정 문자열을 확인하는 함수가 있습니다. 바로 contains인데요. 이번에 함께 사용법을 정리해보겠습니다.

boolean contains(CharSequence s)

대상 문자열에 특정 문자열이 포함되어 있는지 확인하는 함수입니다.
대소문자를 구분합니다.

String str5 = "자바 스프링";
System.out.println(str5.contains("스프링")); //true

📌 String substring()

String substring(int index)
String substring(int startIndex, int endIndex)

문자열을 특정 부분을 잘라내는 함수입니다.
int index 위치의 문자를 포함한 문자열을 반환합니다.
int startIndex는 포함, int endIndex는 미포함입니다.

String str6 = "012345";
System.out.println(str6.substring(3)); //345

String str7 = "자바배우기";
System.out.println(str7.substring(2)) //배우기

			 //01234
String str8 = "Hello";
System.out.println(str7.substring(2,4)) // ll

✍ 풀이

방법1 String

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        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 answer;
    }
}

방법2 HashSet

import java.util.HashSet;

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

방법3 HashMap

import java.util.HashMap;

class Solution {
    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< map.size(); i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))) return false;
            }
        }
        
        return true;
        
    }
}