글 읽기 - 로직이 같아 보이는데 왜 시간 차이가 이렇게나 날까요?

makusta 1년 전 0

제가 보기에는 두 코드의 로직이 크게 다를 게 없어 보이는데 하나는 시간초과가 나고, 하나는 60ms대의 빠른 시간이 나오네요.

리턴받은 걸 바로 다음번 mix에 넘기는 부분과 리턴받은 값을 복사한 후에 mix에 넘기는 부분에 차이가 있어서 해당 로직을 바꿔봤습니다. 하지만 여전히 시간 초과입니다. produce를 쓴다고 해서 그렇게 빨라지는 것도 아니고 이렇게 실행시간이 차이가 나는 이유가 뭘까요? 카드 섞는 로직도 다를 게 없어보여서 이유를 알 수가 없네요

# 다른 분의 코드 (실행시간 60ms대)
import sys
from itertools import product as p

def twoTwo(lis, k):
    print(lis)
    if k == 0: return lis[::-1]
    return twoTwo(lis[-1*2**k:], k-1)+lis[:-1*2**k]

n = int(input())
ori = [i for i in range(1, n+1)]
tar = list(map(int, sys.stdin.readline().split()))
k = 1
while n > 1:
    k += 1
    n //= 2
for i in p([i for i in range(1, k)], repeat=2):
    if tar == twoTwo(twoTwo(ori[:], i[0]), i[1]):
        print(*i)
        break
        

# 제 코드 (시간 초과)
import sys
input = sys.stdin.readline

def sol():
    n = int(input())
    final = list(map(int, input().split()))

    cards = list(range(1, n+1))

    def mix(cards, i):
        print(cards)
        if len(cards) == 1:
            return cards
        return mix(cards[-i:], i//2) + cards[:-i]

    
    for k1 in range(1, (n+1)//2):
        midRes = mix(cards[:], 2**k1)
        for k2 in range(1, (n+1)//2):
            res = mix(midRes[:], 2**k2)
            if final == res:
                print(k1, k2)
                return

sol()
        

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

문제

문제

출처

ICPC

로직이 같아 보이는데 왜 시간 차이가 이렇게나 날까요?

makusta 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말