글 읽기 - C99 1966번 시간초과 해결할 수 있을까요?

jth403 2년 전 0

구조체 배열을 만들어서 인덱스와 우선순위를 저장하고

각 우선순위 개수를 담은 배열을 만들었습니다.

우선순위 9부터 개수가 0이면 continue 로 생략하고

0이 아니라면 pop 할 때마다 개수를 감소해 0이되면 중단합니다.

pop 할 때 원하는 index가 나오면 출력한 뒤 반복문 탈출하는 코드입니다.

시간초과를 줄이기 위해 어떤 것을 더 고려하면 좋을까요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int head = -1, tail = -1;

struct person
{
    int index;
    int rank;
};

struct person Q[101];

void push(struct person P)
{
    tail = (tail + 1) % 101;
    Q[tail].rank = P.rank;
    Q[tail].index = P.index;
}

struct person pop()
{
    head = (head + 1) % 101;
    return Q[head];
}

int main()
{
    int T = 0;
    scanf("%d", &T);
    for (int i = 0; i < T; i++)
    {
        int N = 0, M = 0, X;
        struct person P = { .index = 0, .rank = 0};
        int arr[10] = { 0, };
        memset(Q, 0, sizeof(struct person) * 101);
        scanf("%d %d", &N, &M);
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &X);
            P.rank = X;
            P.index = j;
            push(P);
            arr[X]++;
        }

        int count = 0, k, exit = 0;
        for (int j = 9; j >= 1; j--)
        {
            if (arr[j] == 0)
                continue;
            else
            {
                while (arr[j] > 0)
                {
                    k = (head + 1) % 101;
                    if (Q[k].rank == j)
                    {
                        count++;
                        arr[j]--;
                        if (Q[k].index == M)
                        {
                            printf("%d\n", count);
                            exit = 1;
                            break;
                        }
                        pop();
                    }
                    else
                    {
                        push(pop());
                    }
                }
                if (exit == 1)
                    break;
            }
        }
    }
    return 0;
}

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

문제

문제

출처

ICPC

C99 1966번 시간초과 해결할 수 있을까요?

jth403 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말