HashSet의 contains보다 if가 더 빠를 수도 있다. (LeetCode. 1456)

리트코드 문제

---

Intuition

해당 문자(char)가 모음(a,e,i,o,u)인지 확인하는 코드가 있었다.

처음에는 모음을 가지고 있는 HashSet을 만들어 contains 메소드를 통해 O(1)의 속도로 모음이 존재하는 지 곧바로 확인하는 방식을 떠올렸다.

 

최악의 경우 영어의 모음 5개를 모두 확인하는 것보다 바로 해시값으로 해시테이블에 접근하여 한번에 데이터 유무(존재한다면 모음)을 판단하는 것이 더 빠르지 않을까라고 생각했기 때문이다.

 

(좌) HashSet을 활용한 모음확인 / (우) if절의 각 조건문을 통한 모음 확인

if의 O(5)보다 HashSet의 contains의 O(1)가 더 느리다.?

 

하지만, if를 활용하여 쇼트서킷 없이 모든 모음을 모두 순환하여 확인하는 경우보다 HashSet을 생성하여 contains여부를 확정적으로 한번 가져오는 동작이 더 긴 것으로 보인다.

 

이는 HashSet의 객체의 경우 해시값을 계산하고, 해시테이블 데이터로 접근한 뒤 해시충돌을 처리하는 등의 내부 처리 비용이 상대적으로 큰 것으로 보인다.

 

반면 if절안에서는 직접적으로 비교가 되기에 메모리를 찾아가는 비용이 들지 않기에 가벼운 동작으로 보여진다.

 

과일깎는데 소잡는 칼 쓴 격

 

 

결과

(좌) HashSet을 활용한 모음 확인 / (우) if절을 활용한 모음확인

 

 

 

깨달은 것

이번 경우에는 두 방향 모두 O(1)의 시간 복잡도를 갖기에 결과적으로 큰 차이로 볼 수 없을지도 모른다.

중요한 것은 같은 시간복잡도를 갖거나 N이 작은 경우 등 다양한 경우에 각 방식의 오버헤드 비용을 고려하는 자세인듯 하다.

 

 

---

+실행 코드

1. HashSet을 통해 모음확인

//모음을 가지고 있는 set생성
Set<Character> set = new HashSet<>();
for(char ch : new char[]{'a','e','i','o','u'}) {
    set.add(ch);
}
...
//sliding하며 set.contains를 통해 모음여부 확인
for(int i=k; i<N; i++) {
    if(set.contains(charArr[i-k])) count--;
    if(set.contains(charArr[i])) count++;
    max = Math.max(max, count);
}

 

 

전체코드

class Solution {
    public int maxVowels(String s, int k) {
        int N = s.length();
        char[] charArr = s.toCharArray();
        
        //모음을 가지고 있는 set생성
        Set<Character> set = new HashSet<>();
        for(char ch : new char[]{'a','e','i','o','u'}) {
            set.add(ch);
        }
        
        int count = 0;
        for(int i=0; i<k; i++) {
            if(set.contains(charArr[i])) count++;
        }
        int max = count;

        for(int i=k; i<N; i++) {
            if(set.contains(charArr[i-k])) count--;
            if(set.contains(charArr[i])) count++;
            max = Math.max(max, count);
        }
        return max;
    }
}

 

 

 

2. if 절의 다중 조건을 활용한 모음확인

//모음 확인 메소드
private boolean isVowel (char c) {
    if (c == 'a' ||
        c == 'e' ||
        c == 'i' ||
        c == 'o' ||
        c == 'u') {
            return true;
        } else {
            return false;
        }   
}

 

 

전체코드

class Solution {
    public int maxVowels(String s, int k) {
        int N = s.length();
        char[] charArr = s.toCharArray();

        int count = 0;
        for(int i=0; i<k; i++) {
            if(isVowel(charArr[i])) count++;
        }
        int max = count;
		
        //Sliding
        for(int i=k; i<N; i++) {
            if(isVowel(charArr[i-k])) count--;
            if(isVowel(charArr[i])) count++;
            max = Math.max(max, count);
        }
        return max;
    }

	//모음 확인 메소드
    private boolean isVowel (char c) {
        if (c == 'a' ||
            c == 'e' ||
            c == 'i' ||
            c == 'o' ||
            c == 'u') {
                return true;
            } else {
                return false;
            }   
    }
}