[3강 누적합>이모스1법> 백준 17611] 런타임에러 질문드립니... - 인프런

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

[3강 누적합>이모스1법> 백준 17611] 런타임에러 질문드립니다!

해결된 질문

작성

221

수정됨

import sys

sys.stdin =  open('BackJoon/3강_누적합/5_17611.txt','r')

input =  sys.stdin.readline
n = int(input())

vertex = [list(map(int, input().split())) for _ in range(n)]

######## (x_min, y_min) -> (0, 0)으로 이동
x_min, x_max = 500000, -500000
y_min, y_max = 500000, -500000
for x,y in vertex:
    x_min = min(x, x_min)
    x_max = max(x, x_max)
    y_min = min(y, y_min)
    y_max = max(y, y_max)

x_diff = 0 - x_min
y_diff = 0 - y_min
for i in range(n):
    vertex[i][0] = vertex[i][0] + x_diff
    vertex[i][1] = vertex[i][1] + y_diff

##### 수평선 조사 (강의에서와 같이 왼쪽으로 돌려서 봄)
vertex_x_incre = sorted(vertex, key = lambda x: (x[0], x[1])) # 

y_range = y_max-y_min+1
x_range = x_max-x_min+1

x_sum_list = [0] * (y_range+1) # x축 방향으로 [1, 0, 0, ..., -1] 더함

for i in range(0,n,2): # 선분은 2개의 꼭지점으로 이루어짐
    v1 = vertex_x_incre[i]
    v2 = vertex_x_incre[i+1]

    if v1[0] != v2[0]: # 디버깅
        print('x point does not match!!')#만약 선분이 직선이 아니라면(혹은 sort가 잘못됨)
        break
    if v1[1] >= v2[1]:
        print('y point does not align!!')#sort가 잘못됨
        print('v1:', v1)
        print('v2:', v2)
        break

    x_sum_list[v1[1]] += 1
    x_sum_list[v2[1]] -= 1

x_sum_list = x_sum_list[:-1] #범위밖의 맨 마지막 -1 자리 버림

prefix = [0]*(y_range+1)
for i in range(y_range):
    prefix[i+1] = prefix[i] + x_sum_list[i]
prefix = prefix[1:]
h = max(prefix)


##### y축 방향으로 조사 (수직선 조사)
vertex_y_incre = sorted(vertex, key = lambda x: (-x[1], x[0]))

y_sum_list = [0] * (x_range+1) # y축 방향으로 [1, 0, 0, ..., -1] 더함

for i in range(0,n,2):
    v1 = vertex_y_incre[i]
    v2 = vertex_y_incre[i+1]
    if v1[1] != v2[1]:
        print('y point does not match!!')
        break
    if v1[0] >= v2[0]:
        print('x point does not align!!')
        print('v1:', v1)
        print('v2:', v2)
        break
    y_sum_list[v1[0]] += 1
    y_sum_list[v2[0]] -= 1

y_sum_list = y_sum_list[:-1]

prefix = [0]*(x_range+1)
for i in range(x_range):
    prefix[i+1] = prefix[i] + y_sum_list[i]
prefix = prefix[1:]

v= max(prefix)
print(max(h,v))

python 코딩-테스트 알고리즘

답변 1

한혜경

질문자

일반 글이 작성이 안되서 댓글로 남깁니다!

백준에서 계속 런타임에러가 나는데 혹시 제 코드 어느 부분에 문제가 있는지 질문드립니다!

챗 GPT한테 물어보고 또 GPT가 생성해주는 테스트 케이스도 모두 통과하는데 백준에서 채점만 하면 런타임 에러가 나네요.

혹시 메모리 문제일까요??

오랜 고민끝에 글 남깁니다 알려주시면 감사하겠습니다!!

코딩 센세

지식공유자

늦게 답변드려서 죄송합니다!

백준에 넣어보니 인덱스 에러가 나네요? 조금 더 살펴보고 추가 답들 달겠습니다. ( 아마도 범위 설정에서 문제가 있지 않을까 싶네요.. )

아래는 제가 제출한 코드인데 혹시라도 참고가 될까해서 올려둡니다 ㅎㅎ

 # https://www.acmicpc.net/problem/17611

# 관찰 :
# 수직이동, 수평이동이 반복된다.
# 위로 기둥이 나오면, 이어서 아래로 기둥이 나온다.
# 가장 우측 지점에 도달하면 suffix로 변경된다. ( 하지만 무시해도 계산된다. )
# 개똥벌레 문제랑 동일한 로직이지만, 수직 + 수평 2번 반복된다.

# 아이디어 :
# 먼저 횡이동을 무시하고 모든 기둥을 나열해서 카운팅 해준다.

# -500,000 ~ 500,000
hn = [0]*1001000
wn = [0]*1001000

# 입력을 먼저 받는 방법(o)
# 입력을 받으면서 하는 방법
height = []
width = []
for n in range(int(input())):
    x, y = map(int, input().split())
    y = y + 500000
    x = x + 500000

    width.append(x)
    height.append(y)


maxW = max(width)
minW = min(width)

maxH = max(height)
minH = min(height)


#마지막줄은 계산하지 못하기 때문에 미리 더해주고 빼준다.
a1, b1 = width[0],width[-2]
a2, b2 = height[0],height[-2]

wn[min(a1,b1)] += 1
wn[max(a1,b1)] -= 1

hn[min(a2,b2)] += 1
hn[max(a2,b2)] -= 1

#반복문을 돌려서 프리픽스를 하기 위해 1과 -1을 더해준다
for i in range(n-1):
    # 홀수는 무조건 x값은 동일, y값만 변경된다.
    # if i % 2 == 0:
    a = min(height[i], height[i+1])
    b = max(height[i], height[i+1])
    if a != b:
        hn[a] += 1
        hn[b] -= 1
    # 짝수는 반대다!
    # if i % 2 == 1:
    c = min(width[i], width[i+1])
    d = max(width[i], width[i+1])
    if c != d:
        wn[c] += 1
        wn[d] -= 1
    
#프리픽스 배열을 만든다.
prefix_h = [0]*1001000
prefix_w = [0]*1001000

# 정답을 출력한다.
# answer = 0
for h in range(minH-2, maxH):
    prefix_h[h+1] = prefix_h[h] + hn[h+1]
    # print("h",prefix_h[h+1])
    # answer = max(answer, prefix_h[h+1])

for k in range(minW-2, maxW):
    prefix_w[k+1] = prefix_w[k] + wn[k+1]
    # print("k",prefix_w[k+1])
    # answer = max(answer, prefix_w[k+1])

print(max(max(prefix_h),max(prefix_w)))

인프런 커뮤니티 질문&답변

[3강 누적합>이모스1법> 백준 17611] 런타임에러 질문드립니다!