c언어 10816번 숫자카드 (2) (백준)

#include <stdio.h>

void shell(int arr[], int count) //shell 정렬, 처음 입력받은 수들을 오름차순으로 정렬
{
	int gap = count/2;
	int key = 0;
	int i, j;
	
	while(1==1)
	{
		if(gap%2 == 0) gap++;
		for(i = gap; i<count; i++)
		{
			key = arr[i];
			for(j = i-gap; j>=0; j = j - gap)
			{
				if(key < arr[j]) arr[j+gap] = arr[j];
				else break;
			}
			arr[j+gap] = key;
		}
		if(gap == 1) break;
		gap /= 2;
	}
}

void shell_2(int (*arr)[3], int count) //두번째로 받은 수들을 오름차순으로 정렬
{                                      //입력받은 순서들은 입력받은 수에 종속되어 있음
	int gap = count/2;
	int key = 0;
	int key_2 = 0;
	int i, j;
	
	while(1==1)
	{
		if(gap%2 == 0) gap++;
		for(i = gap; i<count; i++)
		{
			key = arr[i][0];
			key_2 = arr[i][1];
			for(j = i-gap; j>=0; j = j - gap)
			{
				if(key < arr[j][0]) {
					arr[j+gap][0] = arr[j][0];
					arr[j+gap][1] = arr[j][1];
				} 
				else break;
			}
			arr[j+gap][0] = key;
			arr[j+gap][1] = key_2;
		}
		if(gap == 1) break;
		gap /= 2;
	}
}

void shell_3(int (*arr)[3], int count) //입력받은 순서들을 다시 오름차순으로 정렬
{                                      //몇 개 있는지를 나타내는 값은 입력받은 순서에 종속
	int gap = count/2;
	int key = 0;
	int key_2 = 0;
	int i, j;
	
	while(1==1)
	{
		if(gap%2 == 0) gap++;
		for(i = gap; i<count; i++)
		{
			key = arr[i][1];
			key_2 = arr[i][2];
			for(j = i-gap; j>=0; j = j - gap)
			{
				if(key < arr[j][1]) {
					arr[j+gap][1] = arr[j][1];
					arr[j+gap][2] = arr[j][2];
				} 
				else break;
			}
			arr[j+gap][1] = key;
			arr[j+gap][2] = key_2;
		}
		if(gap == 1) break;
		gap /= 2;
	}
}

int main(void)
{
	int n, m;
	scanf("%d", &n); //처음엔 몇 개?
	int n_input[n];
	for(int i = 0; i<n; i++) scanf("%d", &n_input[i]); //first input
	
	shell(n_input, n); //정렬
	
	scanf("%d", &m); //그 다음엔 몇 개?
	int m_input[m][3];
    for(int i = 0; i<m; i++) //second input
	{
		scanf("%d", &m_input[i][0]);
		m_input[i][1] = i;
		m_input[i][2] = 0;
	}
	shell_2(m_input, m); //정렬
	
	
	
	for(int i = 0, j = 0; i<n && j<m; ) //같은 수 찾기
	{
		if(n_input[i] == m_input[j][0]) m_input[j][2]++; //서로 같으면 1 증가
        
		if(n_input[i] > m_input[j][0]) j++; //처음 입력 받은 수가 더 크면, 두번째로 입력받은 것을 그 다음으로
		else i++; //두번째로 입력받은 것이 더 크거나 같으면, 처음 입력 받은 것들 그 다음 번째 걸로 이동
	}
	//두번째에 입력받은 것 들 중 중복이 있는가?
	for(int i = 1; i<m; i++) 
        if(m_input[i-1][0] == m_input[i][0]) m_input[i][2] = m_input[i-1][2];
	
	shell_3(m_input, m); //정렬
	//답 출력
	for(int i = 0; i<m; i++) printf("%d ", m_input[i][2]);

	return 0;
}

 

풀이 : 정수 M개가 주어지고, 여기서 상근이가 주어진 M개의 정수들을 몇 개씩 가지고 있는지를 푸는 문제이다.

단순하게 보면 주어진 M개의 정수를 각각 하나씩 상근이의 N개의 수와 비교해도되나, 시간 복잡도 : N*M, (N, M의 최댓값은 500000)  이므로 너무 오래 걸린다.

 

그래서 상근이의 수와, 입력받은 M개의 수를 각각 오름차순으로 정렬 한 다음 (나는 shell sorting으로 했다)

두 수를 가장 작은 수 부터 비교를 했다.

 

• 비교

1. n_input[i] == m_input[j][0]) m_input[j][2]++;

//서로의 수의 값이 같다면, 특정 수에 대해서 같은 수가 몇 개인지를 의미하는 변수를 1 증가시킨다.

 

2. if(n_input[i] > m_input[j][0]) j++; //상근이의 수가 더 크다면, M개 입력받은 수의 정렬에서 다음 걸 가져온다.
else i++; //M개 입력받은 (지금 비교되는) 수가 더 크다면, 상근이의 수의 수의 정렬에서 다음 걸 가져온다.

 

 

• 중복 

M개 입력받은 수의 정렬에선 중복이 있을 수 있다. 가령

ex) 5

     5 1 2 5 5

     3

     5 5 2

로 입력을 받았다면,

 

정렬로 인해서

     1 2 5 5 5

     2 5 5

가 되며,

   

    출력 값

    3 0 1

 

로 나오게 된다.

 

원래는 3 3 1로 나와야 한다. 왜냐, 상근이의 수에는 5가 3개 있기 때문이다.

이렇듯 M개 입력받은 수에 중복이 있으나, 한 곳에만 같은 값이 있다고 나오기 때문에,

M개 입력 받은 수 중 서로 같은 것이 있다면, 가장 큰 값을 대입해준다. 

 

• 출력

처음에, 입력받은 순서대로 정렬을 한 후, 답을 출력하면 된다.

 

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

10816번: 숫자 카드 2