글 읽기 - c++ 시간초과 이유를 모르겠습니다.

alswp450 3년 전 0

나름 힙정렬? 이용해서 정렬해보았는데도 시간초과가 뜨네요..ㅜㅜ

이유알려주실분 계신가요

#include<iostream>
#include<vector>
#include <string>
// #include<algorithm> // sort,
// #include<string.h> // memset, 

using namespace std;

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
    int testCase;
    vector <int> Age;
    vector <string> Name;

    cin >> testCase;
    while (testCase--) {
        int age;
        string name;
        cin >> age >> name;
        Age.push_back(age);
        Name.push_back(name);
    }

    for (int i = Age.size() - 1; i > 0; i--) {
        int k = i;
        while (k > 0) {
            int idx = (k - 1) / 2; // idx 가 부모, k가 자식
            if (Age[k] < Age[idx]) {
                int temp = Age[idx];
                Age[idx] = Age[k];
                Age[k] = temp;

                string tmp = Name[idx];
                Name[idx] = Name[k];
                Name[k] = tmp;
            }
            k--;
        }
        int num = Age[0];
        Age[0] = Age[i];
        Age[i] = num;

        string s = Name[0];
        Name[0] = Name[i];
        Name[i] = s;

    }


    for (int i = 0; i < Age.size(); i++) {
        cout << Age[i] << " " << Name[i] << "\n";
    }

}

adxx 3년 전 0

N이 최대 10만이고, 시간제한이 3초라서 N^2풀이로는 시간초과가 당연해보이네요

alswp450 3년 전 0

힙정렬은 nlogn 으로 알고있는데 힙정렬 구현방식이 잘못된건가요?? 잘몰라서...

adxx 3년 전 0

구현에 대한 설명이 없어서 잘은 모르겠지만...

힙소트 구현은 원래 구성하는 부분이 있고 다른거 하나가 더 필요하지 않나요?

그나저나 문제의 조건중 stable하게 정렬을 하라고 했으니, 힙정렬로는 못풀 것 같네요

alswp450 3년 전 0

아하.. 감사합니다!! 혹시 다른방식으로 푼것도 봐주실수있나요..ㅜ 예제나 제가 넣는값은 다맞는데 틀렸다고 뜨는지 모르겠어서..

#include<iostream>
#include<vector>
#include <string>
#include<algorithm> // sort,
// #include<string.h> // memset, 

using namespace std;

class Student {
public:
    int age;
    string name;
    Student(int age,string name){
        this->age = age;
        this->name = name;
    }
    int getAge() {
        return age;
    }
    string getName() {
        return name;
    }
}; 
bool compare(Student a, Student b) {
    if (a.getAge() < b.getAge()) {
        return true;
    }
    else {
        return false;
    }
}

int main() {
	cin.tie(nullptr);
    cout.tie(nullptr);
	ios::sync_with_stdio(false);
    int testCase;
    vector <Student> std;

    cin >> testCase;
    while (testCase--) {
        int age;
        string name;
        cin >> age >> name;
        Student a(age, name);
        std.push_back(a);
    }
    sort(std.begin(), std.end(),compare);
    
    for (int i = 0; i < std.size(); i++) {
        cout << std[i].getAge() << " " <<  std[i].getName() << "\n";
    }

}

adxx 3년 전 1

마찬가지로 stable sort를 하지 않으셨네요

sort(std.begin(), std.end(),compare); 이 부분을

stable_sort(std.begin(), std.end(),compare); 이렇게 해주셔야죠

alswp450 3년 전 0

감사합니다!!! 많은 도움 된거같아요!!

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

문제

문제

출처

ICPC

c++ 시간초과 이유를 모르겠습니다.

alswp450 3년 전 0

adxx 3년 전 0

alswp450 3년 전 0

adxx 3년 전 0

alswp450 3년 전 0

adxx 3년 전 1

alswp450 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말