글 읽기 - 1764 듣보잡. C언어) 9%틀렸습니다.

blou888 2년 전 0

처음으로 질문을 작성 해 보는데, 이번에는 반례를 못찾겠어서, 질문을 남겨 봅니다.

먼저 제 코드는 짜다 보니 사전 역순으로 정렬이 되어서, 마지막 for문에서 N-1 부터 시작해서 사전 순으로 돌렸습니다.

혹시 코드 부분에서 잘못 된 부분이나 반례를 찾도록 도와 주실 수 있습니까??

다른 질문들에 있는 반례들은 다 잘 돌아가는 것 같습니다.

(제 전체 적인 코드는,

듣도 입력 받으면서 힙 만들기 -> 정렬하기(사전 역순) -> 보도 입력 받으면서 arr의 인덱스 저장 하기 -> 출력하기.)

코딩의 신들에게 부탁드립니다 ㅠㅠ

#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>

char arr[500000][21];
int idx[500001];

void heaptify(char* value, int end) { //힙을 입력 받으면서 만들어 줍니다.
	char name[21] = "";
	strcpy(arr[end], value);
	while (end > 0) {
		int root = (end - 1) / 2;
		int val = strcmp(arr[end], arr[root]);
		if (val <= -1) {
			char temp[21] = "";
			strcpy(temp, arr[end]);
			strcpy(arr[end], arr[root]);
			strcpy(arr[root], temp);
		}
		else break;
		end = root;
	}
}

void sort(int end) { //마지막 인덱스와 처음 인덱스를 바꿔주고 다시 힙을 만듦. 사전 역순으로 만들어진다.
	while (end > 0) {
		char temp[21] = "";
		strcpy(temp, arr[0]);
		strcpy(arr[0], arr[end]);
		strcpy(arr[end], temp);
		end--;
		int root = 0;
		while (root < end) {
			int child = root * 2 + 1;
			if (strcmp(arr[child], arr[child + 1]) >= 1 && child + 1 <= end) child++;
			if (strcmp(arr[root], arr[child]) != -1) {
				char val[21] = "";
				strcpy(val, arr[root]);
				strcpy(arr[root], arr[child]);
				strcpy(arr[child], val);
			}
			else break;
			root = child;
		}
	}
}

int find_name(char* name, int start, int end) { //이진 탐색으로 찾는다. 그리고 arr에 저장 된 인덱스를 리턴 한다.
	int mid = (start + end) / 2;
	int value = strcmp(arr[mid], name);
	if (value == 0) return mid;
	else if (end <= start) return -1;
	else if (value != -1) return find_name(name, mid + 1, end);
	else if (value != 1) return find_name(name, start, mid);
}

int main()
{
	int N, M;
	int count = 0;
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		char name[21] = "";
		getchar();
		scanf("%s", name);
		heaptify(name, i);
	}

	sort(N - 1);

	for (int i = 0; i < M; i++) {
		char name[21] = "";
		getchar();
		scanf("%s", name);
		int value = find_name(name, 0, N - 1);
		if (value != -1) { 
			idx[value] = 1;
			count++;
		}
	}
	printf("%d\n", count);
	for (int i = N-1; i >= 0; i--) {
		if(idx[i]==1) printf("%s\n", arr[i]);
	}
}

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

문제

문제

출처

ICPC

1764 듣보잡. C언어) 9%틀렸습니다.

blou888 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말