알고리즘 Contains 시간복잡도에 대한 정보 HashMap/ArrayList

알고리즘중

값을 배열에 저장하는 로직에서

값의 존재여부를 조회할때

ArrayList 의 contain 를 사용하게 되면 
collection 매서드의 동작에서 ArrayList 의 길이 n 만큼 O(n) 만큼 순회하게된다.

이런 케이스는 많은 시간복잡도를 요구한다.

HashMap으로 치환이가능한 알고리즘이라면

HashMap의 키에 값을 넣고 키를 가지고있는지 조회하면

HashMap의 containkey 타입으로 확인을 하면

key 값의 메모리 주소를 바로 찾기 때문에 O(1) 단한번의 연산으로 끝낼수있다

import java.util.ArrayList;

public class Scartch {
    public int solution(int[] A) {
        ArrayList<Integer>arrayList = new ArrayList<>();
        for (int i=0; i<A.length; i++){
            int num = A[i];
            if (!arrayList.contains(num)){
                arrayList.add(num);
            }else {
                arrayList.remove(Integer.valueOf(num));
            }
        }
        return arrayList.get(0);
    }
}

ArrayList 의 contains 를 적용한모습

for문안에 들어가있어서 O(n^2) 의 시간복잡도

public class Scartch {
    public int solution(int[] A) {
        HashMap<Integer,Boolean>hashMap = new HashMap<>();
        for (int i=0; i<A.length; i++){
            int num = A[i];
            if (!hashMap.containsKey(num)){
                hashMap.put(num,true);
            }else {
                hashMap.remove(num);
            }
        }
        int answer=0;
        for (int a: hashMap.keySet()){
            if (hashMap.get(a)==true){
                answer=a;
            }
        }
        return answer;
    }
}

해쉬맵의 contains 키를 적용한 알고리즘이다

O(n)으로시간복잡도를 줄인 상황이다