글 읽기 - 시간초과 나는 이유가 무엇인가요?

rhwnsrb1223 4년 전 0

실행 값은 제대로 출력이 되는데,

시간초과 에러가 발생합니다.

저의 생각으로는 sort를 하기에 발생하는 문제같은데,

그 문제가 맞다면, 이와같은 문제는 어떻게 해결해야하나요?

또한, 그것이 아니라면 어떤 방법을 사용해야할지 감이 오지않습니다 ㅠ

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

int main(int argc, char * argv[]) {
    int testcase;
    std::cin >> testcase;

    std::vector <int> x_in; // 입력받은 x를 저장할 벡터
    std::vector <int> y_in; // 입력받은 y를 저장할 벡터

    for (int i = 0; i < testcase; i++) {
        int x, y;
        std::cin >> x >> y;
        x_in.push_back(x);  // x 입력
        y_in.push_back(y);  // y 입력
    }

    for (int i = 0; i < x_in.size(); i++) {
        std::sort (x_in.begin(), x_in.end());   // x의 value를 오름차순으로 정렬
        std::sort (y_in.begin(), y_in.end());   // y의 value를 오름차순으로 정렬
    }

    for (int i = 0 ; i< x_in.size(); i++) 
        std::cout << x_in[i] << " " << y_in[i] << std::endl;   
    return 0;
}

cheshirecoder 4년 전 0

정상 작동하지 않으므로 문제를 잘 읽고 다시 잘 생각해보기 바랍니다.

ploffer11 4년 전 0

일단 알고리즘 로직이 틀렸습니다. 그런데 틀렸습니다가 아닌 시간초과가 나는 이유는 endl을 써서 그런 것 같습니다.

endl을 "\n" 으로 바꾸시고

main문 바로 아래에

cin.tie(0);

ios::sync_with_stdio(0);

도 추가해주시면 틀렸습니다를 받을 수 있을 것입니다.

portableangel 4년 전 0

지금 작성하신 코드는 x좌표와 y좌표를 따로 정렬하는 작업을 입력받은 점의 개수만큼 반복하는 코드입니다.

O(NlogN) 정렬을 N번 하신 데다, 입출력 량이 꽤 많은데 cin, cout, endl 등의 느린 입출력 함수를 사용하신 점까지 시간 초과의 요소가 됩니다.

우선 정렬은 N번 할 필요가 없고, X와 Y의 값을 묶어서 정렬해야 합니다. 지금은 예를 들어, 점이 세 개

1 3

2 2

3 1

이 존재한다면, x좌표를 따로 정렬하고 y좌표를 따로 정렬하여

1 1

2 2

3 3

이 됩니다. 그런데 입력된 점에는 (1,1)도 없고 (3,3)도 없습니다.

페어(std::pair)로 묶어서 정렬하시거나, 구조체를 이용해 보세요.

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

문제

문제

출처

ICPC

시간초과 나는 이유가 무엇인가요?

rhwnsrb1223 4년 전 0

cheshirecoder 4년 전 0

ploffer11 4년 전 0

portableangel 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말