글 읽기 - [파이썬] string -> int로 변환해서 구했는데, TL이 발생합니다.

wnsrl4067 2년 전 1

입력받는 숫자의 배수가 "1"로만 이루어져 있는지 검사하는 것보단, "1"로만 이루어져 있는 숫자들이 입력받는 숫자로 나누어 지는지 확인하는게 빠를것 같아서, 아래와 같이 구현을 하였습니다.

num을 string 형태로 "1"씩 붙여가면서, int로 형변환 해주고, 나누어질때, num의 길이를 출력해주는 형식으로 구현하였습니다.

num = num*10 + 1 이라는 숫자로 계산하는 법도 알고 있는데, string으로 처리해도 큰 차이는 없을 것 같아 제출했는데 TL이 떠서 질문을 남깁니다.

string -> int로 형변환 O(len(str))이 걸리는 걸로 알고 있는데, 왜 TL이 뜨는지 모르겠습니다.

1억자리(1억개의 )1로 이루어진 수 때문일까요..

import sys
input =sys.stdin.readline
num="1"

while True:
    try:
        N=int(input().rstrip())
    except:
        break
    while True:
        int_num=int(num)
        if int_num%N==0:
            print(len(num))
            break
        num+="1"

lcr7324 2년 전 2

num += "1" 연산이 매우 무거운 연산이라 그렇습니다. list의 append처럼 O(1)으로 동작하지 않고 O(n)으로 동작합니다.

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

wnsrl4067 2년 전 0

헛.. O(N)으로 동작을 하는군요.. string은 스트링을 하나하나 다시 복사하는 과정이 필요하다는걸 잠시 망각했네요. 감사합니다 :)

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

문제

문제

출처

ICPC

[파이썬] string -> int로 변환해서 구했는데, TL이 발생합니다.

wnsrl4067 2년 전 1

lcr7324 2년 전 2

wnsrl4067 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말