2024-08-31

• 백준 1764번 : 듣보잡을 풀다가 새로운 사실을 알게 되었다. 처음에 ArrayList 로 풀었는데 시간 초과가 났다. 그런데 HashSet 으로 바꾸기만 했는데 통과되는게 아닌가? 원인은 ArrayList와 HashSet 에서의 contains() 함수 시간복잡도 차이에 있었다. ArrayList의 contains()는 시간복잡도가 O(n)인데 반해, HashSet의 contains()는 시간복잡도가 O(1)이다. contains()함수가 HashSet의 경우 Hashmap을 기반으로 구현되어 있지만, ArrayList는 indexOf()를 이용해 포함 여부를 판단하기 때문이다. indexOf()의 경우 전체 배열 내부를 순회하며 포함 여부를 검사하기 때문에 최악의 경우 마지막까지 순회하게 되므로 이런 일이 벌어지는 것이다. 효율성이 요구되는 문제를 풀 때는 ArrayList 대신 HashSet을 사용하는 것이 좋겠다.

• Detroit : Become Human 엔딩을 봤다. 통계를 보니 소수의 선택을 한 듯하다. 무엇보다 안드로이드가 인류를 지배했다. 썩 마음에 드는 결말이 아닌데.. 다른 엔딩을 시도해봐야겠다.

작성한 문서

• Playings