성준이의 개발블로그 성준이의 개발블로그

문제 링크https://www.acmicpc.net/problem/1920아이디어이번 문제는 시간복잡도를 줄이며 두번째 숫자 모음에 있는 숫자들이 첫번 째 숫자 모음에 있는지 탐색하는 문제라는 생각이 들었습니다. 어떻게 시간복잡도를 줄일지 생각하다가, 처음에는 이진 탐색이 생각 났습니다. 그런데 이것은 정렬이 선행되어야 했고, 정렬의 평균적 시간 복잡도는 O(nlogn)이기 때문에 좀 더 빠른 방법이 없을지 고민해 봤습니다. 그러다가 배열을 set함수를 사용해 집합으로 바꿔 평균 O(n)시간복잡도로 중복을 제거하고, 평균 O(1) 시간복잡도로 탐색하면 더 빠를 거 같아 set함수를 이용한 탐색을 사용하기로 결정했습니다. 문제 해결의 아이디어는1. 두번째 줄의 숫자들을 arr배열에 저장해둡니다.2. 중복을..