글 읽기 - 사냥꾼 질문

whgkdrjs4321 4년 전 0

이 문제에 대해서 계속해서 시간초과가 뜨는데 혹시 어떻게 해야 이 오류를 해결할 수 있을까요?

참고로 일부러 pair를 안 사용하고 풀어보기 위해서 선택정렬로 x,y를 정렬했습니다.

#include <iostream>
#include <algorithm>
using namespace std;

int gun[100001];					//사대의 x좌표
int x[100001];						//동물의 x좌표
int y[100001];						//동물의 y좌표

int distance(int x, int a, int b)	//사대와 동물사이의 거리
{
	int val;

	if (x > a)
		return (x - a + b);
	else
		return (a - x + b);
}


int main()
{
	int m, n, l;						//m : 사대의 수, n : 동물의 수, l : 사정거리
	int idx = 0;						//x를 오름차순으로 정렬할 때의 인덱스로 사용
	int index = 0;						//gun의 인덱스로 사용
	int cnt = 0;						//잡을 수 있는 동물의 수

	cin >> m >> n >> l;

	for (int i = 0; i < m; i++)
		cin >> gun[i];

	for (int i = 0; i < n; i++)
		cin >> x[i] >> y[i];

	sort(gun, gun + m);					//사대를 오름차순 정렬

	for (int i = 0; i < n; i++)			//x[i]를 기준으로 오름차순 정렬 -> 선택정렬
	{
		int min = 1000000001;

		for (int j = i; j < n; j++)
		{
			if (min > x[j])
			{
				min = x[j];
				idx = j;
			}
		}

		int tmp1 = x[i];
		x[i] = x[idx];
		x[idx] = tmp1;

		int tmp2 = y[i];
		y[i] = y[idx];
		y[idx] = tmp2;
	}

	for (int i = 0; i < n; i++)			//동물의 위치를 기준으로 살핀다.
	{
		while (index != m - 1 && gun[index + 1] < x[i])	//동물의 위치의 x값(x[i])보다 왼쪽에 있는 사대의 위치 중 가장 가까운 위치를 찾음.
			index++;									//그래서 gun[index+1]의 위치를 살펴봄.
	
		if (distance(gun[index], x[i], y[i]) <= l)		//동물의 위치보다 왼쪽or 같은 x좌표의 사대를 비교
		{
			cnt++;
			continue;
		}

		if (index != m - 1)
		{
			if (distance(gun[index + 1], x[i], y[i]) <= l)		//동물의 위치보다 (왼쪽+1)의 사대를 비교
			{
				cnt++;
				continue;
			}
		}
	}

	cout << cnt << endl;

	return 0;
}

djm03178 4년 전 1

N이 10만인 문제에 O(N^2)인 선택 정렬을 사용하셨기 때문에 당연히 시간 초과가 됩니다.

whgkdrjs4321 4년 전 0

pair를 안 쓰려고 하다보니 x,y를 별개의 배열로 선언할 수 밖에 없었고, 그것을 정렬하다보니 O(n*m)이 필연적으로 사용될 수 밖에 없는 것 같습니다.

혹시라도 sort를 안 쓰고 위의 코드처럼 정렬할 수 있으면서 시간초과가 안 날 수 있는 방법이 있을까요?

djm03178 4년 전 1

pair를 안 썼다는 것은 단지 원소를 옮길 때 x와 y를 같이 옮기면 될 뿐이고, 그 때문에 정렬 알고리즘에 영향을 줄 부분은 전혀 없습니다.

병합 정렬을 하든, 힙 정렬을 하든 원소를 옮기는 순간에 같이 옮기는 방식으로 O(NlogN)의 정렬을 하면 됩니다. std::sort가 마법을 부려서 O(NlogN)인 것이 아니고 그냥 이런 평범한 정렬 알고리즘들을 섞어서 씁니다.

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

문제

문제

출처

ICPC

사냥꾼 질문

whgkdrjs4321 4년 전 0

djm03178 4년 전 1

whgkdrjs4321 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말