[C]백준_4158 : CD

Alal11·2023년 3월 19일

출처

https://www.acmicpc.net/problem/4158

문제

상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. CD의 번호는 십억을 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0 0이 주어진다.

상근이와 선영이가 같은 CD를 여러장 가지고 있는 경우는 없다.

출력

두 사람이 동시에 가지고 있는 CD의 개수를 출력한다.

예제 입출력

알고리즘 분류

자료 구조
이분 탐색
해시를 사용한 집합과 맵
두 포인터

➡️문제 분석

상근이와 선영이의 각 CD는 오름차순으로 정렬되어 있으므로 배열을 이용하여 CD 번호의 크기를 비교한다. 더 작은 쪽의 배열의 인덱스를 +1씩 해주는 것으로 크기가 같은 경우를 찾을 수 있다.

➡️코드(⭕)

#include <stdio.h>
#include <stdlib.h>			// malloc, free 함수가 포함된 헤더 파일

int main()
{
	while (1)
	{
		int n, m;			// 상근이와 선영이의 CD의 수
		
		scanf("%d %d", &n, &m);

		if (n == 0 && m == 0)
			break;

		int* arr1 = (int*)malloc(sizeof(int)*n);
		int* arr2 = (int*)malloc(sizeof(int)*m);

		// 상근이와 선영이의 CD의 번호 입력받음 (오름차순)
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &arr1[i]);
		}
		for (int i = 0; i < m; i++)
		{
			scanf("%d", &arr2[i]);
		}

		int ptr1 = 0, ptr2 = 0;		// 양쪽 배열 인덱스를 가리킬 각 ptr변수 선언
		int cnt = 0;

		// 양쪽 ptr이 배열을 넘지 않을 때까지 반복
		while (ptr1 < n && ptr2 < m)
		{
			// ptr1이 ptr2보다 작으면 ptr1를 +1 해줌
			if (arr1[ptr1] < arr2[ptr2])
				ptr1++;
			// ptr2가 ptr1보다 작으면 ptr2를 +1 해줌
			else if (arr1[ptr1] > arr2[ptr2])
				ptr2++;
			// 양쪽 ptr이 같으면 공통 CD의 개수를 세어주고, 양쪽 ptr을 +1씩 해줌
			else
			{
				cnt++;
				ptr1++;
				ptr2++;
			}
		}
		printf("%d\n", cnt);

		free(arr1);
		free(arr2);
	}
	return 0;
}

➡️코드 분석

여러 개의 테스트 케이스로 이루어져 있기 때문에 무한 반복문으로 n과 m을 입력받는데, 둘 다 0과 0이 입력되면 반복문을 빠져나온다.
n과 m의 크기만큼 동적 메모리 할당을 해주고, 상근이와 선영이의 CD의 수(n, m) 만큼 반복하여 각각의 CD의 번호를 배열로 입력받는다.
양쪽 배열 인덱스를 가리킬 ptr1과 ptr2를 선언하고 0으로 초기화 시켜준다.
양쪽 ptr이 CD의 수를 넘지 않을 때까지 반복해준다.

배열은 오름차순으로 입력받았기 때문에 arr1[ptr1]과 arr2[ptr2]의 크기를 비교하여 작은 쪽의 ptr을 +1을 해준다.

만약, 양쪽 ptr이 같으면 공통 CD의 개수를 세어주는 cnt를 +1해주고, ptr1과 ptr2를 동시에 +1씩 해준다.
위 과정을 CD 수만큼 반복해준 다음 cnt을 출력해주고, 동적 메모리를 각각 반납해준다.