글 읽기 - 반례 부탁드립니다.

rakwon1617 1년 전 0

알려주시면 감사하겠습니다:D

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct search {
	int rank;
	int data;
	int cnt;
}search;

int card[500000];
search k[500000];

int compare(const void* a, const void* b) {
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 < num2)
		return -1;
	
	if (num1 > num2)
		return 1;
	
	return 0;
}

int cmp_data(const void* a, const void* b) {

	search* x, * y;

	x = (search*)a;
	y = (search*)b;

	if (x->data < y->data)
		return -1;
	if (x->data > y->data)
		return 1;
	return 0;
}

int cmp_rank(const void* a, const void* b) {

	search* x, * y;

	x = (search*)a;
	y = (search*)b;

	if (x->rank < y->rank)
		return -1;
	if (x->rank > y->rank)
		return 1;
	return 0;
}

int main()
{
	int n, m;
	int i, j;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
		scanf("%d", &card[i]);

	scanf("%d", &m);

	for (i = 0; i < m; i++) {
		scanf("%d", &k[i].data);
		k[i].rank = i;
		k[i].cnt = 0;
	}

	qsort(card, n, sizeof(int), compare);
	qsort(k, m, sizeof(search), cmp_data);

	i = 0;
	j = 0;

	while (1) {
		if (card[i] == k[j].data) {
			k[j].cnt += 1;
			i += 1;
		}
		else if (card[i] > k[j].data) {
			j += 1;
		}
		else if (card[i] < k[j].data) {
			i += 1;
		}

		if (i == n) {
			while (1) {
				j += 1;
				if (j == m)
					break;

				if (k[j].data == k[j - 1].data)
					k[j].cnt = k[j - 1].cnt;
				else
					break;
				
			}
			break;
		}
		if (j == m)
			break;
	}

	qsort(k, m, sizeof(search), cmp_rank);

	for (i = 0; i < m; i++)
		printf("%d ", k[i].cnt);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다.

rakwon1617 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말