MZ 개발자

이 문제는 상근이가 가지고 있는 숫자 카드 N개 중 주어진 M(정수)를 몇개씩 가지고 있는지 구한는 문제이다. N은 -10,000,000 ~ 100,000,000 사이의 숫자로 중복된 값이 들어올 수 있다. 이를 해결하기 위해 N개의 카드 중 특정 숫자가 몇개 존재하는지 체크를 해야한다. 가장 간단한 방법은 카드에 적혀 있는 숫자를 배열의 인덱스로 하여 카운팅 해주는게 편리한데 그렇게 할 경우 인덱스 범위가 0~ 200,000,000이 되어 해당 크기의 배열을 정의할 수 없다. 따라서 다른 방법을 생각해야한다. 생각해낸 방법은 백터를 이용하여 N을 정렬한 후 순차 탐색하면서 이전의 값이랑 중복되는지 안되는지 확인하여 새로운 해싱 백터를 만드는 것이다. 자세한 방법은 아래 코드에서 확인할 수 있다. 위의 ..

이 문제는 N개의 카드중에서 M개의 카드 숫자가 몇개 있는지 찾는 문제이다. 단순한게 브루트포스 방법 O(n^2)으로 문제를 해결하려고 시도한다면 N = 500000, M = 500000 이므로 시간초과가 발생한다. 따라서 특정 숫자가 어디에 있는지 빠르게 탐색하기 위해 이진탐색으로 접근해야 한다. 이진탐색을 하기 위해서는 우선 상근이의 숫자 카드 N이 오름 차순으로 정렬이 되어있어야 한다. 이때 핵심은 중복된 숫자 카드를 어떻게 표현할 것인가 이다. 오름 차순 정렬 후 앞쪽부터 순회하면서 중복된 숫자를 pair 로 변환 시켜준다. 예를들어 N이 -10, -10, 1, 3, 5, 10, 10, 10 일경우 {-10,2}, {1,1}, {3,1}, {5,1}, {10,3} 과 같은 형태로 변환을 시켜준다...