글 읽기 - 9466 시간초과, 메모리초과

kjuny00 1년 전 0

안녕하세요,

문제를 첫번째 사람부터 n까지 사이클이 생기는가 체크하는 식으로 한번 확인한건 기록해서 다시 확인하지 않도록 하였습니다.

근데도 계속해서 시간초과가 나서 몇번을 고쳐봤지만 계속해서 78-79퍼대에서 시간초과가 나서 이유가 cycle함수에서 while (find(history.begin(), history.end(), i) == history.end()){ 문에서 find를 반복해서 그런가 싶어서 그 부분을 고쳐봤는데 그러니까 반대로 메모리초과가 납니다… 딱히 크게 바꾼건 없는데 왜 메모리초과가 나는건지도 모르겠습니다.

위 코드는 시간초과 코드, 아래 코드는 메모리초과 코드입니다.

어느 이유로 시간초과와 메모리초과가 나는 것인지 제 알고리즘이 잘못된건지 알려주시면 감사드리겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <climits>

using namespace std;

int pick[100001];
bool pass[100001];
int numb, n;
pair<vector<int>, int> cycle(int i){
    vector<int> history;
    int start = i;
    while (find(history.begin(), history.end(), i) == history.end()){
        if (pass[i])
            return {history, -1};
        if (i == pick[i]){
            pass[i] = true;
            numb--;
            return {history, -1};
        }
        history.push_back(i);
        i = pick[i];
    }
    return {history, i};
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--){
        cin >> n;
        numb = n;
        for (int i = 1; i <= n; i ++){
            cin >> pick[i];
            pass[i] = false;
        }
        pair<vector<int>, int> k;
        vector<int> history;
        int start;
        for (int i  = 1;  i <=n; i++){
            if (pass[i])
                continue;
            if (pick[i] == i){
                pass[i] = true;
                numb--;
            }
            else{
                k = cycle(i);
                history = k.first;
                start = k.second;
                for (int a : history)
                    pass[a] = true;
                for (int j = 0; j < history.size(); j++){
                    if (history[j] == start){
                        numb -= history.size() - j;
                        break;
                    }
                }
            }
        }
        cout << numb << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <climits>

using namespace std;

int pick[100001];
bool pass[100001];
int numb, n;
pair<vector<int>, bool> cycle(int i){
    vector<int> history;
    int start = i;
    while(true){
        if (pass[i])
            return {history, false};
        if (i == pick[i]){
            pass[i] = true;
            numb--;
            return {history, false};
        }
        history.push_back(i);
        i = pick[i];
        if (start == i)
            break;
    }
    return {history, true};
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--){
        cin >> n;
        numb = n;
        for (int i = 1; i <= n; i ++){
            cin >> pick[i];
            pass[i] = false;
        }
        bool b;
        pair<vector<int>, int> k;
        vector<int> history;
        for (int i  = 1;  i <=n; i++){
            if (pass[i])
                continue;
            if (pick[i] == i){
                pass[i] = true;
                numb--;
            }
            else{
                k = cycle(i);
                history = k.first;
                b = k.second;
                for (int a : history)
                    pass[a] = true;
                if (b)
                    numb -= history.size();
            }
        }
        cout << numb << endl;
    }
    return 0;
}

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

문제

문제

출처

ICPC

9466 시간초과, 메모리초과

kjuny00 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말