Shiny Sky Blue Star

백준 문제 풀이/백준 (C)

C 백준 1920 수 찾기 (이분탐색)

gamja00 2024. 6. 30. 15:59

 

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

 

문제

  1. 첫째 줄에 수 N(1 <= N<= 100000) 입력
  2. 둘째 줄에 A[1], A[2], ..., A[N]개의 정수 입력 (배열)
  3. 셋째 줄에 수 N(1 <= M <= 100000) 입력
  4. 넷째 줄에 M개의 정수 입력
  5. 마지막에 주어진 M개의 정수가 A(배열) 안에 존재하는지(존재시 1, 존재않을시 0)를 출력.

 

처음 만든 코드.
이전에 만들었던 이분탐색 코드를 기반으로 main 코드 부분과 searchNode 코드를 추가했음.

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

#define maxSize 100000

typedef struct Node {	//노드 구조체 선언
	int data;
	struct Node* leftChild;
	struct Node* rightChild;
}Node;

Node* new_Node(int key) {		//노드 생성하는 함수
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드를 동적할당.
	newNode -> data = key;
	newNode -> leftChild = NULL;
	newNode -> rightChild = NULL;

	return newNode; //노드를 가리키는 포인터 반환. 포인터를 반환해야 노드 안의 원소로 접근이 가능.
}

Node* insertNode(Node* root, int key) { //루트랑 비교하여 값을 추가하는 부분
	if (root == NULL) {
		root = new_Node(key);
		return root;
	}
	else if (root -> data > key) // key 값이 root 보다 작다면 왼쪽 서브트리로
		root -> leftChild = insertNode(root -> leftChild, key);
	else if (root -> data < key)  // key 값이 root 보다 크다면 오른쪽 서브트리로
		root -> rightChild = insertNode(root -> rightChild, key);
	return root;
}

Node* searchNode(Node* root, int key) {	//루트랑 비교하여 값을 찾는 부분
	if (root -> data == NULL) { //키값 존재시
		printf("0\n");
	}
	if (root -> data == key)	//키값 존재시
		printf("1\n");
	else {
		if (root -> data > key)  // key 값이 root 보다 작다면 왼쪽 서브트리
			searchNode(root -> leftChild, key);
		else if (root -> data < key)  // key 값이 root 보다 크다면 오른쪽 서브트리
			searchNode(root -> rightChild, key);
	}
}

int main(void) {
	int N, M, num;
	Node* root = NULL;
	int A[maxSize];

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &num);
		root = insertNode(root, num);
	}

	scanf_s("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &num);
		searchNode(root, num);
	}

	return 0;
}

 

 

출력 결과는 이렇게 나온다.

출력 결과가 1, 새로 입력한 수가 기존의 정수 배열에 들어있을 경우는 제대로 출력이 되었음.
출력 결과가 0일 때 오류가 발생하는 것으로 보아 null과 관련된 오류로 보인다.

 

이 오류가 맞는 것 같으니 오류 수정

 

수정한 코드

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

typedef struct Node {	//노드 구조체 선언
	int data;
	struct Node* leftChild;
	struct Node* rightChild;
}Node;

Node* new_Node(int key) {		//노드 생성하는 함수
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드를 동적할당.
	newNode -> data = key;
	newNode -> leftChild = NULL;
	newNode -> rightChild = NULL;

	return newNode; //노드를 가리키는 포인터 반환. 포인터를 반환해야 노드 안의 원소로 접근이 가능.
}

Node* insertNode(Node* root, int key) { //루트랑 비교하여 값을 추가하는 부분
	if (root == NULL) {
		root = new_Node(key);
		return root;
	}
	else if (root -> data > key) // key 값이 root 보다 작다면 왼쪽 서브트리로
		root -> leftChild = insertNode(root -> leftChild, key);
	else if (root -> data < key)  // key 값이 root 보다 크다면 오른쪽 서브트리로
		root -> rightChild = insertNode(root -> rightChild, key);
	return root;
}

Node* searchNode(Node* root, int key) {	//루트랑 비교하여 값을 찾는 부분
	if (root != NULL) {
		if (root->data == key) { //키값 존재시
			return printf("1\n");
		}
		else {
			if (root->data > key)  // key 값이 root 보다 작다면 왼쪽 서브트리
				searchNode(root->leftChild, key);
			else if (root->data < key)  // key 값이 root 보다 크다면 오른쪽 서브트리
				searchNode(root->rightChild, key);
		}
	}
	else { //키값 존재시
		printf("0\n");
	}
}

int main(void) {
	int N, M, num;
	Node* root = NULL;

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &num);
		root = insertNode(root, num);
	}

	scanf_s("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &num);
		searchNode(root, num);
	}

	return 0;
}

 

출력은 잘 되나 시간 초과

 

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

typedef struct Node {	//노드 구조체 선언
	int data;
	struct Node* leftChild;
	struct Node* rightChild;
}Node;

Node* new_Node(int key) {		//노드 생성하는 함수
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새로운 노드를 동적할당.
	newNode -> data = key;
	newNode -> leftChild = NULL;
	newNode -> rightChild = NULL;

	return newNode; //노드를 가리키는 포인터 반환. 포인터를 반환해야 노드 안의 원소로 접근이 가능.
}

Node* insertNode(Node* root, int key) { //루트랑 비교하여 값을 추가하는 부분
	if (root == NULL) {
		root = new_Node(key);
		return root;
	}
	else if (root -> data > key) // key 값이 root 보다 작다면 왼쪽 서브트리로
		root -> leftChild = insertNode(root -> leftChild, key);

	else if (root -> data < key)  // key 값이 root 보다 크다면 오른쪽 서브트리로
		root -> rightChild = insertNode(root -> rightChild, key);

	return root;
}

Node* searchNode(Node* root, int key) {	//루트랑 비교하여 값을 찾는 부분
	if (root != NULL) {
		if (root -> data == key)  //키값 존재시
			return printf("1\n");

		else if (root -> leftChild != NULL && root -> leftChild -> data == key)  // leftChild 값이 key 값이면 존재하는 것이므로 1 출력
			return printf("1\n");

		else if (root -> rightChild != NULL && root -> rightChild -> data == key)  // rightChild 값이 key 값이면 존재하는 것이므로 1 출력
			return printf("1\n");

		else {
			if (root -> data > key)  // key 값이 root 보다 작다면 왼쪽 서브트리
				searchNode(root -> leftChild, key);

			else if (root -> data < key)  // key 값이 root 보다 크다면 오른쪽 서브트리
				searchNode(root -> rightChild, key);
		}
	}
	else { //키값 존재 않을시
		printf("0\n");
	}
}

int main(void) {
	int N, M, num;
	Node* root = NULL;

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &num);
		root = insertNode(root, num);
	}

	scanf_s("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &num);
		searchNode(root, num);
	}

	return 0;
}

 

search 부분에서 루트값을 포함한 좌우 노드 값이 키 값일 때 바로 출력되도록 해봤는데 시간초과가 여전히 떠서 어떻게 줄여야 될지 모르겠다...
이 구조를 유지하면서 시간을 줄일 수 없을까...

 

#include <stdio.h>

int temp[100000]; // 병합에 필요한 임시 배열

void merge(int array[], int low, int mid, int high) {

	int L, M, H;
	L = low;
	M = mid + 1;
	H = low;

	// 배열을 정렬
	while (L <= mid && M <= high) {
		if (array[L] <= array[M])
			temp[H++] = array[L++];
		else
			temp[H++] = array[M++];
	}

	// 두 배열 병합
	if (L > mid) {
		for (int i = M; i <= high; i++)
			temp[H++] = array[i];
	}
	else {
		for (int i = L; i <= mid; i++)
			temp[H++] = array[i];
	}


	for (int i = low; i <= high; i++) {// 임시배열을 원래에 배열로 복사
		array[i] = temp[i];
	}
}

void merge_sort(int array[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;  // 중간을 기준으로 리스트 분할
		merge_sort(array, low, mid); // 앞 리스트 정렬
		merge_sort(array, mid + 1, high); // 뒤 리스트 정렬
		merge(array, low, mid, high); // 정렬된 배열 병합
	}
}

void find(int array[], int N, int number) {
	for (int i = 0; i < N; i++) {
		if (array[i] == number) {
			printf("1\n");
			break;
		}
		if (i == N - 1) {
			printf("0\n");
		}
	}
}

int main(void) {
	int N, M, num;
	int arr[100000];

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}

	merge_sort(arr, 0, N - 1);

	scanf("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf("%d", &num);
		find(arr, M, num);
	}

	return 0;
}


병합 정렬... 써봤는데 탈락함

#include <stdio.h>

int temp[100000]; // 병합에 필요한 임시 배열

void merge(int array[], int low, int mid, int high) {

	int L, M, H;
	L = low;
	M = mid + 1;
	H = low;

	// 배열을 정렬
	while (L <= mid && M <= high) {
		if (array[L] <= array[M])
			temp[H++] = array[L++];
		else
			temp[H++] = array[M++];
	}

	// 두 배열 병합
	if (L > mid) {
		for (int i = M; i <= high; i++)
			temp[H++] = array[i];
	}
	else {
		for (int i = L; i <= mid; i++)
			temp[H++] = array[i];
	}


	for (int i = low; i <= high; i++) {// 임시배열을 원래에 배열로 복사
		array[i] = temp[i];
	}
}

void merge_sort(int array[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;  // 중간을 기준으로 리스트 분할
		merge_sort(array, low, mid); // 앞 리스트 정렬
		merge_sort(array, mid + 1, high); // 뒤 리스트 정렬
		merge(array, low, mid, high); // 정렬된 배열 병합
	}
}

void find(int array[], int N, int number) {
	int low = 0, high = N - 1, mid;
	mid = (low + high) / 2;

	while (1) {
		if (mid < low || mid > high) {
			printf("0\n");
			break;
		}
		if (number == array[mid]) {
			printf("1\n");
			break;
		}
		else if (number > array[mid]) {
			mid++;
		}
		else {
			mid--;
		}
	}
}

int main(void) {
	int N, M, num;
	int arr[100000];

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &arr[i]);
	}

	merge_sort(arr, 0, N - 1);

	scanf_s("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &num);
		find(arr, M, num);
	}

	return 0;
}

이분탐색까지!!!!!!!!

ㅋㅋ ㅡㅡ
니가 이기나 내가 이기나 해보자

#include <stdio.h>

int temp[100000]; // 병합에 필요한 임시 배열

void merge(int array[], int low, int mid, int high) {

	int L, M, H;
	L = low;
	M = mid + 1;
	H = low;

	// 배열을 정렬
	while (L <= mid && M <= high) {
		if (array[L] <= array[M])
			temp[H++] = array[L++];
		else
			temp[H++] = array[M++];
	}

	// 두 배열 병합
	if (L > mid) {
		for (int i = M; i <= high; i++)
			temp[H++] = array[i];
	}
	else {
		for (int i = L; i <= mid; i++)
			temp[H++] = array[i];
	}


	for (int i = low; i <= high; i++) {// 임시배열을 원래에 배열로 복사
		array[i] = temp[i];
	}
}

void merge_sort(int array[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;  // 중간을 기준으로 리스트 분할
		merge_sort(array, low, mid); // 앞 리스트 정렬
		merge_sort(array, mid + 1, high); // 뒤 리스트 정렬
		merge(array, low, mid, high); // 정렬된 배열 병합
	}
}

int main(void) {
	int N, M, num;
	int arr[100000];

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &arr[i]);
	}

	merge_sort(arr, 0, N - 1);

	scanf_s("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &num);

		int low = 0, high = M - 1, mid;
		mid = (low + high) / 2;

		for (int i = 0; i < M; i++){
			if (mid < low || mid > high) {
				printf("0\n");
				break;
			}
			if (num == arr[mid]) {
				printf("1\n");
				break;
			}
			else if (num > arr[mid]) {
				mid++;
			}
			else {
				mid--;
			}
		}
	}

	return 0;
}

크아아아아아아아악 뭐가 문제야

#include <stdio.h>

int temp[100000]; // 병합에 필요한 임시 배열

void merge(int array[], int low, int mid, int high) {

	int L, M, H;
	L = low;
	M = mid + 1;
	H = low;

	// 배열을 정렬
	while (L <= mid && M <= high) {
		if (array[L] <= array[M])
			temp[H++] = array[L++];
		else
			temp[H++] = array[M++];
	}

	// 두 배열 병합
	if (L > mid) {
		for (int i = M; i <= high; i++)
			temp[H++] = array[i];
	}
	else {
		for (int i = L; i <= mid; i++)
			temp[H++] = array[i];
	}


	for (int i = low; i <= high; i++) {// 임시배열을 원래에 배열로 복사
		array[i] = temp[i];
	}
}

void merge_sort(int array[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;  // 중간을 기준으로 리스트 분할
		merge_sort(array, low, mid); // 앞 리스트 정렬
		merge_sort(array, mid + 1, high); // 뒤 리스트 정렬
		merge(array, low, mid, high); // 정렬된 배열 병합
	}
}

int main(void) {
	int N, M, num;
	int arr[100000];

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &arr[i]);
	}

	merge_sort(arr, 0, N - 1);

	scanf_s("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &num);

		int low = 0, high = M - 1, mid;
		mid = (low + high) / 2;

		while (1){
			if (mid < low || mid > high) {
				printf("0\n");
				break;
			}
			if (num == arr[mid]) {
				printf("1\n");
				break;
			}
			else if (num > arr[mid]) {
				mid++;
			}
			else {
				mid--;
			}
		}
	}

	return 0;
}

질문 게시판을 보니까 시간 초과가 무한 루프일 수도 있다고 해서... 고쳐봤는데 또 시간초과가 뜬다...

의지의 한국인
불굴의 한국인

최종 코드

#include <stdio.h>

int temp[100000]; // 병합에 필요한 임시 배열

void merge(int array[], int low, int mid, int high) {

	int L, M, H;
	L = low;
	M = mid + 1;
	H = low;

	// 배열을 정렬
	while (L <= mid && M <= high) {
		if (array[L] <= array[M])
			temp[H++] = array[L++];
		else
			temp[H++] = array[M++];
	}

	// 두 배열 병합
	if (L > mid) {
		for (int i = M; i <= high; i++)
			temp[H++] = array[i];
	}
	else {
		for (int i = L; i <= mid; i++)
			temp[H++] = array[i];
	}


	for (int i = low; i <= high; i++) {// 임시배열을 원래에 배열로 복사
		array[i] = temp[i];
	}
}

void merge_sort(int array[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;  // 중간을 기준으로 리스트 분할
		merge_sort(array, low, mid); // 앞 리스트 정렬
		merge_sort(array, mid + 1, high); // 뒤 리스트 정렬
		merge(array, low, mid, high); // 정렬된 배열 병합
	}
}

int main(void) {
	int N, M, num;
	int arr[100000];

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &arr[i]);
	}

	merge_sort(arr, 0, N - 1);

	scanf_s("%d", &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &num);

		if (num > arr[N - 1]) { // 1차 필터링(1)
			printf("0\n");
		}
		else if (num < arr[0]) { // 1차 필터링(2)
			printf("0\n");
		}
		else {
			int low = 0, high = N - 1, mid= (low + high) / 2; // 여기서 M이 아니라 N으로 고침 M != N 을 고려하지 않았던 것도 있다.
			
			while (1) { // 2차 필터링
				mid = (low + high) / 2;
				
				if (mid < low || mid > high) {
					printf("0\n");
					break;
				}
				if (num == arr[mid]) {
					printf("1\n");
					break;
				}
				else if (num > arr[mid]) {
					low = mid + 1;
				}
				else {
					high = mid - 1;
				}
			}
		}
	}

	return 0;
}


진짜... 해냈다 그냥...
노력했다 진짜로다가...

틀린 이유는... 시간 초과랑... 무한루프... 때문인 것 같다. 질문 게시판에서 찾은 반례에서 답이 안 나왔으니까 아마 그거지 않을까 싶다.

'백준 문제 풀이 > 백준 (C)' 카테고리의 다른 글

C 백준 25206 너의 평점은 (심화 1)  (0) 2024.07.01
C 백준 1753 최단경로 (최단 경로) - 미완  (0) 2024.07.01
C 백준 1026 보물 (수학)  (0) 2024.06.30
C 백준 11718 그대로 출력하기 (문자열)  (0) 2024.06.30
C 백준 1316 그룹 단어 체커 (문자열)  (0) 2024.06.30

'백준 문제 풀이/백준 (C)'의 다른글

  • 현재글C 백준 1920 수 찾기 (이분탐색)

관련글

티스토리툴바