String.equals와 HashSet contains의 시간복잡도 비교 (프로그래머스 전화번호 목록)

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

프로그래머스

import java.util.HashSet;
class Solution {

    public HashSet<String> set = new HashSet<>();
    public boolean solution(String[] phone_book) {
        
        boolean answer = true;
        for(String number : phone_book){
            set.add(number);
        }
        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;
    }
}

 

 

equals 로 String 비교하는것 보다 set으로 contains 여부를 확인하는게 더 시간복잡도가 낮다
어쩌면 당연하게도 String.equals는 각 byte 혹은 char 단위로 비교를 하고 있었다.
즉, 시간 복잡도는 O(1)이 아니라 문자열 길이에 따라 다른 O(N)에 해당한다.
그에비해 Hashset에서 contains는 O(1)에 해당된다.

 

String.equals	HashSet (contains)	ArrayList (contains)	LinkedList (contains)
O(N)	O(1)	O(N)	O(N)