글 읽기 - 시간 초과의 이유를 전혀 모르겠습니다.

kemin1910 1년 전 0

한 for문 안에 cin과 cout를 번갈아가면서 써준 것도 아닌데 어째서 시간 초과가 발생하는지 궁급합니다.

#include <iostream>
using namespace std;

int x[100001];
int y[100001];

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = i; j < N; j++) {
			if (y[i] > y[j]) {
				int tmp_y;
				int tmp_x;
				tmp_y = y[j];
				y[j] = y[i];
				y[i] = tmp_y;
				tmp_x = x[j];
				x[j] = x[i];
				x[i] = tmp_x;
			}
			else if ((y[i] == y[j]) && (x[i] > x[j])) {
				int tmp_x;
				tmp_x = x[j];
				x[j] = x[i];
				x[i] = tmp_x;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		cout << x[i] << " " << y[i] << '\n';
	}

	return 0;
}

pill27211 1년 전 1

N (1 ≤ N ≤ 100,000)이고 시간 제한이 1초라서 애초에 통과할 수 없는 코드입니다. sort함수에 대해 공부해 보세요.

kemin1910 1년 전 0

코드를 이렇게 고쳐보았는데 아예 for문이 들어가면 안되는 것일까요? 또 시간 초과가 납니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<pair<int, int>> xy;
	int x, y;

	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		xy.push_back({ y, x });
	}

	sort(xy.begin(), xy.end());

	for (int i = 0; i < N; i++) {
		for (int j = i; j < N; j++) {			
			if ((xy[i].first == xy[j].first) && (xy[i].second > xy[j].second)) {
				int tmp_xy;
				tmp_xy = xy[j].second;
				xy[j].second = xy[i].second;
				xy[i].second = tmp_xy;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		cout << xy[i].second << " " << xy[i].first << '\n';
	}

	return 0;
}

pill27211 1년 전 1

ios_base ::sync_with_stdio(false);(C와 버퍼 동기화를 끊음)

cin.tie(NULL);

cout.tie(NULL);

(cin과 cout을 untie)

cin과 cout을 사용하실 경우 위 문장을 main함수 최상단에 삽입하면 속도가 빨라집니다.

또한, 벡터의 push_back은 기본적으로 O(1)이지만 기존 용량(capacity)를 넘을 경우 O(N)만큼의 시간복잡도를 갖습니다.(더 큰 공간(*2)을 잡고 기존 벡터를 복사, 해제) 벡터의 요소가 추가되면 될수록(capacity를 넘을 때마다) O(N)의 연산을 계속 하게 되겠죠. -> 최초 선언에서 vector <pair<int, int>> xy(N);(애초에 입력받을 크기만큼 할당) 로 바꿔주면 되겠죠?

마지막으로, 21번 코드부터의 for문은 사실상 필요치 않습니다. sort함수에 정렬 기준을 직접 정의하면 되기 때문이지요.(sort함수 한 번 사용으로 문제의 정렬 기준 모두 충족 가능) 아래에 예시코드 참고해 주제요. 생략을 좀 했지만 이해는 충분히 되실 겁니다.

typedef struct _Point
{
    int xpos;
    int ypos;
}Point;

bool Compare(Point p1, Point p2)
{
    if(p1.ypos == p2.ypos)//만약 y좌표가 같다면 x좌표를 기준으로 오름차순 정렬.
        return p1.xpos < p2.xpos;
    return p1.ypos < p2.ypos;//y좌표를 기준으로 오름차순 정렬.
}

(main 함수에서)
sort(arr.begin(), arr
end(), Compare);
//직접 정의한 정렬 기준은 세번째 인자로 주면됨.

kemin1910 1년 전 1

이해하기 쉬운 설명 감사합니다. bool Compare가 자주 보인다 했는데 sort함수에서 조건을 정하는 대표적인 기법 중 하나로 쓰이고 있더라구요.

pill27211 1년 전 1

맞아요. sort의 디폴트 퍼포먼스는 오름차순이지만, 정렬 조건을 직접 정의할 수 있다는 점에서 그 활용도가 무궁무진하죠.(숫자, 나아가 문자 및 문자열 등등)

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

문제

문제

출처

ICPC

시간 초과의 이유를 전혀 모르겠습니다.

kemin1910 1년 전 0

pill27211 1년 전 1

kemin1910 1년 전 0

pill27211 1년 전 1

kemin1910 1년 전 1

pill27211 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말