만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

카드 교환

면접 대비

시간 제한2초메모리 제한512 MB

요약
정렬된 두 카드 더미가 주어질 때, 서로 가지고 있지 않은 서로 다른 종류의 카드를 각각 N장씩 교환할 수 있는 최대 N을 구한다.
난이도

쉬움10점 중 3점

유형
투 포인터, 배열, 해시맵
정답자
아직 제출이 없습니다

문제

앨리스와 베아트리스는 포켓몬 카드를 모은다. 이 카드로 하는 배틀 게임도 있지만, 두 사람은 아직 어려서 게임은 하지 않고 카드 자체에만 관심이 있다. 카드에는 정수 번호가 하나씩 붙어 있고, 번호가 같은 카드는 같은 종류로 본다.

두 사람은 각자 카드를 여러 장 가지고 있고, 서로 카드를 바꾸고 싶어 한다. 교환에는 두 가지 조건이 있다. 둘 다 가지고 있는 종류의 카드는 바꾸지 않는다. 그리고 교환으로 받는 카드에 같은 종류가 두 장 이상 들어가면 안 된다. 교환은 한 번에 끝난다. 앨리스가 종류가 서로 다른 카드 NN장을 베아트리스에게 건네고, 베아트리스도 종류가 서로 다른 카드 NN장을 앨리스에게 건넨다.

두 사람이 주고받을 수 있는 NN의 최댓값을 구하는 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 앨리스가 가진 카드의 개수 AA와 베아트리스가 가진 카드의 개수 BB가 공백 하나로 구분되어 주어진다 (1≤A≤1041 \le A \le 10^4, 1≤B≤1041 \le B \le 10^4). 둘째 줄에는 앨리스가 가진 카드의 번호 XiX_i가 AA개, 공백으로 구분되어 주어진다 (1≤Xi≤1051 \le X_i \le 10^5). 셋째 줄에는 베아트리스가 가진 카드의 번호 YiY_i가 BB개, 공백으로 구분되어 주어진다 (1≤Yi≤1051 \le Y_i \le 10^5). 두 사람의 카드 번호는 각각 비내림차순으로 주어진다.

입력의 마지막 줄에는 00 두 개가 공백 하나로 구분되어 주어진다. 이 줄은 테스트 케이스가 아니다.

출력

각 테스트 케이스마다 앨리스와 베아트리스가 서로 주고받을 수 있는 카드 수의 최댓값을 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    1 1
    1000
    1000
    3 4
    1 3 5
    2 4 6 8
    10 9
    1 1 2 3 5 7 8 8 9 15
    2 2 2 3 4 6 10 11 11
    0 0
    
    예상 출력
    0
    3
    4