글 읽기 - 오늘 알고리즘 A문제 시간초과...

qkreltms 5년 전 0

2%에서 넘어가질 않습니다.

시간초과가 나오는데 도데체 어디서 그렇게 오래걸리는지 모르겠네요...

1. 오름차순이 아니면 뒤집는다 -> 오름차순으로 만듬

2. 1 2 3 4 5 ->  5 1 2 3 4 -> 4 5 1 2 3 n만큼 돌면서 이런식으로 b배열의 자리를 바꾸면서 a배열과 배열 배치가 같은지 찾는다.

3. 중간에 배열 배치가 같으면 바로 출력하고 종료

4. n번을 다 돌았는데도 불구하고 찾지 못 한다면 bad puzzle 출력

from sys import stdin


def f(n, a, b):
    if a[0] > a[1]:
        a = a[::-1]
    if b[0] > b[1]:
        b = b[::-1]

    while n:
        if a == b:
            print("good puzzle")
            return;
        b.insert(0, b.pop())
        n -= 1
    print("bad puzzle")


n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
b = list(map(int, stdin.readline().split()))

f(n, a, b)

jh05013 5년 전 1

a = a[::-1], a == b, b.insert(0, x) 모두 O(N)의 시간이 걸립니다.

qkreltms 5년 전 1

기껏 해봐야

O(N^2)정도 나오는데 이렇게 느린가요?

jh05013 5년 전 0

C++과 Pypy (더 빠르게 돌아가는 파이썬) 기준 O(N^2)로는 N <= 10000 근처가 한계입니다.

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

문제

문제

출처

ICPC

오늘 알고리즘 A문제 시간초과...

qkreltms 5년 전 0

jh05013 5년 전 1

qkreltms 5년 전 1

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말