글 읽기 - C 시간초과

h301701 1년 전 0

삽입 정렬을 쓰니 시간초과가 나네요

어떤 정렬을 써야 할까요?

#include <stdio.h>

int main(void){
    
    int n;
    scanf("%d", &n);

    int num[100005][2] = {0, };
    for (int i = 0; i < n; i++){
        scanf("%d %d", &num[i][0], &num[i][1]);
    }

    int i, j;
    for (i = 1; i < n; i++){
        int key_x = num[i][0];
        int key_y = num[i][1];
        for (j = i-1; j >= 0 && num[j][0]>key_x; j--){
            num[j+1][0] = num[j][0];
            num[j+1][1] = num[j][1];
        }
        num[j+1][0] = key_x;
        num[j+1][1] = key_y;
    }

    for (i = 1; i < n; i++){
        int key_x = num[i][0];
        int key_y = num[i][1];
        for (j = i-1; j >= 0; j--){
            if (num[j][0] == key_x && num[j][1]>key_y){
                num[j+1][0] = num[j][0];
                num[j+1][1] = num[j][1];
            }
            else {
                break;
            }
        }
        num[j+1][0] = key_x;
        num[j+1][1] = key_y;
    }

    for (int i = 0; i < n; i++){
        printf("%d %d\n", num[i][0], num[i][1]);
    }

    return 0;
}

amsminn 1년 전 0

삽입정렬의 시간복잡도는 O(n^2)입니다

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

문제

문제

출처

ICPC

C 시간초과

h301701 1년 전 0

amsminn 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말