import sys
input = sys.stdin.readline
N = int(input())
nums = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
total = 0
for j in range(N):
if i == j:
continue
if nums[i][0] != nums[j][0] and nums[i][1] > nums[j][1]:
total += nums[j][1]
print(total)
단순한 루프 연산으로 코드를 짜도 값은 나온다. 하지만 시간 복잡도가 이중포문이므로 O(N^2)이다.
import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
nums = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
result = []
for i in range(N):
result.append(list(filter(lambda x : x[0]
if nums[i][0] != x[0] and nums[i][1] > x[1]
else None, nums[:i]+nums[i+1:])))
for res in result:
print(sum([row[1] for row in res]))위 코드는 오답이다. 그럼 왜 포스팅하느냐? 결과는 정답 + 파이서닉함이라서다. 이 코드가 오답인 이유는 시간과 메모리를 고려하지 않았기 때문이다.
먼저 nums[:i]+nums[i+1:]에서 O(N^2)번 값의 복사가 일어나기 때문에 비효율적이다.
다음으로 result를 배열로 저장하기 때문. 해당되는 값을 다 넣기 때문에 result가 메모리를 많이 잡아 먹는다. 여기도 최대 O(N^2)
그치만 파이서닉하게 짜면 이렇게도 적을 수 있음을 기록한다.
import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
nums = [tuple(map(int, sys.stdin.readline().split())) + (i,) for i in range(N)]
nums.sort(key=lambda x : x[1])
# print(nums)
color_sum = dict()
answer = [0]*N
j = 0
total = 0
for i in range(N):
color, size, idx = nums[i]
while j < N and nums[j][1] < size:
c, s, _ = nums[j]
total += s
color_sum[c] = color_sum.get(c,0) + s
j += 1
answer[idx] = total - color_sum.get(color, 0)
for idx in answer:
print(idx)최종 통과 코드이다. (1) 크기별로 정렬해서 (2) 같은 색 공은 제외 (3) 원래 인덱스 순서로 출력 단계를 지켜서 짜주자. 근데 이 방법도 처음에 똑같이 시간초과가 났다.
지피티가 말해준 원인은 sys.stdin.readline() 대신 input()을 사용한 것이 가장 크다고 한다. 정말 그 부분만 고치니까 해결이 되었다.
공부