글 읽기 - 1744번 수묶기 파이썬 시간초과 질문입니다.

psj1028 3년 전 1

여러 테스트 케이스를 수행해봤고 시간초과가 나왔습니다.

의심되는 부분은 arr.sort(reverse=Ture) 와

arr.reverse()인데..

혹시 이외에 제가 놓친 시간 복잡도가 있을까요?

아래는 제가 생각한 문제 풀이입니다.

1. 내림차순으로 정렬

2. 음수가 있는지 확인하고 있을 경우 끝의 두 수를 pop하여 곱해서 양수로 만든 후 ans에 더함

3.다시 역순으로 배치

4. 반복문을 돌며 최대한 끝의 두 수를 pop하여 곱한 후 업데이트

- 이 때 곱하지 않아야 하는 케이스인 0, 1에 대해서 예외처리 완료.

- 음수가 1개 남아 있는 경우와 0이 같이 있는 경우 0과 음수를 곱하는 예외처리 완료.

어떤 부분에서 시간초과가 나는지 도저히 모르겠습니다..

코드를 10번정도 수정했는데 어렵네요 ㅠㅠ

sort의 시간복잡도도 O(n*logn) 이고 reverse는 O(n)이며, pop은 O(1)로 알고 있습니다..

from sys import stdin
n = int(stdin.readline())
arr = [0] * n
ans = 0
for i in range(n):
    arr[i] = int(stdin.readline())
if n == 0:
    print(0)
    exit()

# 음수 제거하기
count_neg = 0
arr.sort(reverse=True)
while arr[-1] < 0 and n > 2:
    if arr[-2] > 0:
        break
    val_1 = arr.pop()
    val_2 = arr.pop()
    n -= 2
    ans += val_1 * val_2
arr.reverse()
n = len(arr)
if n != 1:

    while n >= 2:
        if arr[-1] == 0 or arr[-2] == 0:
            break
        if arr[-1] == 1 or arr[-2] == 1:
            ans += arr[-1] + arr[-2]
            arr.pop()
            arr.pop()
            n -= 2
            continue
        elif arr[-2] > 0:
            ans += arr[-1]*arr[-2]
            arr.pop()
            arr.pop()
            n -= 2

    if n > 1:
        if arr[-2] > 0 and arr[-1] < 0:
            ans += (arr[-2] + arr[-1])
            arr.pop()
            arr.pop()
            n -= 2

        elif arr[-1] == 0:
            ans += (arr[-2] * arr[-1])
            arr.pop()
            arr.pop()
            n -= 2

if n != 0:
    if n%2 != 0 and arr[-1] != 0:
        ans += arr[-1]
print(ans)

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

문제

문제

출처

ICPC

1744번 수묶기 파이썬 시간초과 질문입니다.

psj1028 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말