글 읽기 - 프로그래밍 언어 자체의 문제로 시간초과 경험 있으신분 있나요? (Python 등)

debuglog 6년 전 0

Python으로 계속 문제 풀고있습니다.

파이썬이 느린건 알고있지만 지금까지 풀던 문제는 파이썬으로 해결가능했는데요.

3163번 문제를 객체지향적으로 한번 풀어봤는데 계속 시간초과 뜨네요 ㅠㅠ

알고리즘상의 문제인가요?

아니면 언어 자체의 문제일수도 있을까요?ㅠㅠ

import sys
read = lambda : sys.stdin.readline().replace('\n', '')

class Ant:
    def __init__(self, pos_, id_):
        self.id = id_
        self.pos = pos_
        self.dir = -0.5 if id_ < 0 else 0.5
        
    def move(self):
        self.pos += self.dir
    
    def change_dir(self):
        self.dir *= -1
        
    def __lt__(self, other):
         return self.pos < other.pos

def check_collide_ant(ants):
    sorted_ants = sorted(ants)
    for i in range(len(sorted_ants)-1):
        if sorted_ants[i].pos == sorted_ants[i+1].pos:
            sorted_ants[i].change_dir()
            sorted_ants[i+1].change_dir()
            
def move_ant(ants):
    for ant in ants:
        ant.move()

def check_out_ant(ants, l, out_ants):
    temp = []
    for ant in ants:
        if ant.pos == 0 or ant.pos == l:
            temp.append(ant)
            ants.remove(ant)
    
    if len(temp) == 2:
        if abs(temp[0].id) > abs(temp[1].id):
            temp.reverse()
    
    out_ants.extend(temp)
       

n = int(read())
for i in range(n):
    an, l, k = map(int, read().split())
    ants = []
    out_ants = []
    for j in range(an):
        ant_pos, ant_id = map(int, read().split())
        ants.append(Ant(ant_pos, ant_id))
        
    while len(out_ants) < k:
        move_ant(ants)
        check_out_ant(ants, l, out_ants)
        check_collide_ant(ants)
    
    sys.stdout.write(str(out_ants[k-1].id)+'\n')

jh05013 6년 전 1

파이썬은 채점할 때 시간을 더 주는 데다가 훨씬 빠른 PyPy라는 것이 있기 때문에 파이썬으로 못 푸는 문제는 거의 없습니다.

알고리즘이 비효율적입니다.

debuglog 6년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

프로그래밍 언어 자체의 문제로 시간초과 경험 있으신분 있나요? (Python 등)

debuglog 6년 전 0

jh05013 6년 전 1

debuglog 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말