[백준] 1946번 문제풀이

문제 : www.acmicpc.net/problem/1946

1946번: 신입 사원

 

알고리즘 : 

1. 왼쪽 기준으로 구조체를 Sorting.

2. 오른쪽에서 1이 나올 때 까지, 왼쪽[0]의 오른쪽 보다 작으면  count++

3. count 출력

 

이렇게 하면 실패한다.

그 이유는 2번에서 왼쪽[0]의 오른쪽이 고정된게 아니고, 왼쪽[0]의 오른쪽보다 더 작은게 나오면 갱신을 시켜줘야한다.

그래야 문제에서 요구하는 조건에 맞을 수 있다.

 

소스코드1(틀린거) : 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_ARR 100001

typedef struct GRADE
{
	int left;
	int right;
}GRADE;

void merge(GRADE* arr, int left, int mid, int right);
void mergeSort(GRADE* arr, int left, int right);

GRADE temp[MAX_ARR];

int main(void)
{
	GRADE arr[MAX_ARR];
	int TC;
	scanf("%d", &TC);
	for (int test_case = 0; test_case < TC; test_case++)
	{
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d %d", &arr[i].left, &arr[i].right);
		}
		for (int i = 0; i < n; i++) { temp[i].left = temp[i].right = 0; }

		mergeSort(arr, 0, n - 1);

		int count = 1;
		for (int i = 1; i < n; i++)
		{
			if (arr[i].right == 1) { count++; break; }
			if (arr[i].right < arr[0].right) { count++; }
		}
		printf("%d\n", count);
	}
	return 0;
}

void mergeSort(GRADE* arr, int left, int right)
{
	if (left == right) { return; }
	int mid = (left + right) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid + 1, right);
	merge(arr, left, mid, right);
	return;
}
void merge(GRADE* arr, int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right)
	{
		if (arr[i].left < arr[j].left)
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid) { temp[k++] = arr[i++]; }
	while (j <= right) { temp[k++] = arr[j++]; }
	for (int a = left; a <= right; a++)
	{
		arr[a] = temp[a];
	}
}

 

소스코드2(맞은거) :

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_ARR 100001

typedef struct GRADE
{
	int left;
	int right;
}GRADE;

void merge(GRADE* arr, int left, int mid, int right);
void mergeSort(GRADE* arr, int left, int right);

GRADE temp[MAX_ARR];

int main(void)
{
	GRADE arr[MAX_ARR];
	int TC;
	scanf("%d", &TC);
	for (int test_case = 0; test_case < TC; test_case++)
	{
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d %d", &arr[i].left, &arr[i].right);
		}

		mergeSort(arr, 0, n - 1);

		int count = 1;
		int leastRank = arr[0].right;
		for (int i = 1; i < n; i++)
		{
			if (arr[i].right == 1) { count++; break; }
			if (arr[i].right < leastRank) { leastRank = arr[i].right; count++; }
		}
		printf("%d\n", count);
	}
	return 0;
}

void mergeSort(GRADE* arr, int left, int right)
{
	if (left == right) { return; }
	int mid = (left + right) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid + 1, right);
	merge(arr, left, mid, right);
	return;
}
void merge(GRADE* arr, int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right)
	{
		if (arr[i].left < arr[j].left)
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid) { temp[k++] = arr[i++]; }
	while (j <= right) { temp[k++] = arr[j++]; }
	for (int a = left; a <= right; a++)
	{
		arr[a] = temp[a];
	}
}

 

시간이 생각보다 너무 오래걸렸다. 748ms나 나왔다.

 

그리고 기존에는 struct GRADE 라고만 정의했는데, 그러니까 컴파일에러가 난다.

따라서 typedef struct GRADE라고 해주어야 한다.

그렇지 않으면, GRADE 자료형을 쓸 때 struct GRADE a; 라고 해줘야한다.

 

왜 VS에서는 되었냐면, 소스코드.cpp로 소스파일을 만들었기 때문에 되었다.

이건 몰랐던거기 때문에 이제부터 참고하면 된다.

 

그리고, 이 문제를 풀다가 안풀려서 인터넷을 보았다. (알고리즘을 참조함)

실제 시험이었으면 떨어졌을 것이다.

안풀린다고 인터넷 검색해보지 말고 TC를 더 만들어서 확인해보자.

 

 

걸린시간 : 76분(18분 알고리즘, 58분 코딩 및 디버깅)