글 읽기 - 이 문제는 파이썬으로 해결할 수 없나요?

aru0504 2년 전 2

안녕하세요. 단순 연결 리스트 구현이라고 생각했다가 데였습니다.

시간초과 받고 나니 파이썬으로 문제를 푼 분이 안 계시다는 것을 깨닫고 문제를 해결해보고자 했는데요

최적화 방법은:

input -> sys.stdin.readline

print -> 한 번에 list에 모아서 sys.stdout.write로 '\n'.join()

이걸로도 해결이 되지 않아서:

혹여나 Node 클래스가 무거울까 봐 dict로만 시도 (아래 코드)

를 해 봤습니다만, 여전히 해결이 되지 않습니다.

언어별 추가 시간이 없어서 파이썬으로는 풀 수 없는 문제일까요?

rkaxhdals 2년 전 1

제가 해보니까 되긴 됩니다만... 파이썬으로 풀기에는 정신건강에 안좋은 듯 합니다.

dict는 해싱을 해야 하기 때문에, list를 쓰세요. 1000000만 칸 list로 구현할 수 있습니다.

그리고 2D list의 arr[][]과 같은 두 번 참조는 1D list를 여러 개 만들어서 한 번 참조하는 게 빠릅니다. 이 문제에서는 이 최적화가 반드시 필요해 보입니다.;

aru0504 2년 전 0

안녕하세요. 도와주셔서 감사합니다!

추가적인 최적화를 진행해봤지만 여전히 시간초과라서 다시 질문드립니다..

- dict -> list로 변경

- node_value, node_next, node_prev 세 개의 리스트를 관리했지만 node_value의 값은 필요없으므로 제거

- 함수 내에 변수 저장하므로 속도 향상 (global 제거)

를 시도했지만.. 통과하지 못했습니다.

추가적인 조언이 있다면 부탁드리겠습니다.

import sys
input = sys.stdin.readline

def main():
    def insert_next_to(self, node):
        nodes_next[node] = nodes_next[self]
        nodes_prev[node] = self
        nodes_prev[nodes_next[self]] = node
        nodes_next[self] = node

    def delete_node(self):
        nodes_next[nodes_prev[self]] = nodes_next[self]
        nodes_prev[nodes_next[self]] = nodes_prev[self]
        nodes_next[self] = nodes_prev[self] = None

    N, M = map(int, input().split())
    arr = list(map(int, input().split()))
    nodes_prev = [None] * 1000001
    nodes_next = [None] * 1000001

    for i in range(N-1):
        nodes_prev[arr[i+1]] = arr[i]
        nodes_next[arr[i-1]] = arr[i]
    nodes_prev[arr[0]] = arr[-1]
    nodes_next[arr[-2]] = arr[-1]

    ans = []
    for i in range(M):
        command, *args = input().split()
        if command == "BN":
            p, q = map(int, args)
            ans.append(nodes_next[p])
            insert_next_to(p, q)
        elif command == "BP":
            p, q = map(int, args)
            ans.append(nodes_prev[p])
            insert_next_to(nodes_prev[p], q)
        elif command == "CN":
            p = int(args[0])
            ans.append(nodes_next[p])
            delete_node(nodes_next[p])
        elif command == "CP":
            p = int(args[0])
            ans.append(nodes_prev[p])
            delete_node(nodes_prev[p])
    print(*ans, sep='\n')

if __name__ == "__main__":
    main()

aru0504 2년 전 0

+ CPP로 해결 후 답변자님 코드 참고했습니다

모르면 풀 수 없는 문제였습니다. pypy에서의 fastio는 처음 봅니다.

위 로직에 fastio만 추가하니 맞았습니다.

감사합니다... 허무하네요

ref: https://stackoverflow.com/ques...

#Fastio for pypy3
#input은 binary 형태로 받기에,string compare는 b""로 해야합니다

import os, io, __pypy__
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ans = __pypy__.builders.StringBuilder()
os.write(1, ans.build().encode())

rkaxhdals 2년 전 1

애초에 저정도 수준의 fastio는 필요 없어야 정상인데... 파이썬이니 악깡버 해야겠죠 ㅠ

아무튼 해결하셨다니 고생 많으셨습니다..!

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

문제

문제

출처

ICPC

이 문제는 파이썬으로 해결할 수 없나요?

aru0504 2년 전 2

rkaxhdals 2년 전 1

aru0504 2년 전 0

aru0504 2년 전 0

rkaxhdals 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말