[Python] 백준 2628번 종이자르기 문제 (+시간복잡도 개선)

백준 2628번 종이자르기 문제를 파이썬으로 풀어보자

 

문제가 너무 깁니다 선생님들.. 

아무튼! 코드를 안보고 짜보려고 했는데 도저히 테스트 케이스 통과가 안됨.

 

# 최초 코드

import sys

h, v = map(int, sys.stdin.readline().split())
n = int(sys.stdin.readline())

for _ in range(n):
  cut_times = list(map(int, sys.stdin.readline().split()))
  h_list = []
  v_list = []
  if cut_times[0] == 0:
    h_list.append(cut_times[1])
  else:
    v_list.append(cut_times[1])

h_list.sort()
v_list.sort()
area = []

for i in range(len(h_list)):
  for j in range(len(v_list)):
    if i == 0 and j == 0:
      a = h_list[i] * v_list[j]
      area.append(a)
    elif i == 0 and j != 0:
      a = h_list[i] * (v_list[j]-v_list[j-1])
      area.append(a)
    elif i != 0 and j == 0:
      a = (h_list[i]-h_list[i-1]) * v_list[j]
      area.append(a)
    else:
      a = (h_list[i]-h_list[i-1]) * (v_list[j]-v_list[j-1])
      area.append(a)

largest = max(area)

print(largest)

 

문제점

1) 자꾸 리스트가 비었다고 하는데.. 도저히 이해가 안간다 싶었음.

가로에서 처음짜른 건 처음 값이 0이어야하는데 그 조건을 elif를 여러번 쓰면서 검사할 필요 없이 

list 자체에 제일 첫번째 줄 값인 0을 넣어주면 되는 일이었다.

 

2) 또 for 문 안에 각 list가 들어있어 계속 초기화되는 것이었다.

 

3) 가로로 자르면, 세로길이에 영향이 가고 

    세로로 자르면, 가로길이에 영향이 간다는 것이다.

 

이걸 간과해서 순서가 서로 뒤바뀌어 있었다.

 

그래서 고친 코드가 아래와 같음.

 

import sys

h, v = map(int, sys.stdin.readline().split())
n = int(sys.stdin.readline())

a_list = [0, h]
b_list = [0, v]

for _ in range(n):
  cut_times = list(map(int, sys.stdin.readline().split()))
  if cut_times[0] == 0:
    b_list.append(cut_times[1])
  else:
    a_list.append(cut_times[1])
a_list.sort()
b_list.sort()
largest = 0

for i in range(1, len(a_list)):
  for j in range(1, len(b_list)):
    width = a_list[i] - a_list[i-1]
    height = b_list[j] - b_list[j-1]
    a = width * height
    largest = max(largest, a)

print(largest)

 

 

근데 백준 solved.ac에 댓글 보니까 너비를 구해서 최댓값을 구할 필요가 없고,

가로길이, 세로길이 제일 큰 것들 구해서 곱하면 그게 젤 큰 너비였던 것.

지금 위의 코드에서는 시간복잡도가 O(n²)였고 (for문을 중첩해서 돌리기 때문)

아래 코드로 개선하면 시간복잡도가 O(n)으로 줄어든다.

 

# 최종 코드

import sys

h, v = map(int, sys.stdin.readline().split())
n = int(sys.stdin.readline())

a_list = [0, h]
b_list = [0, v]

for _ in range(n):
  cut_times = list(map(int, sys.stdin.readline().split()))
  if cut_times[0] == 0:
    b_list.append(cut_times[1])
  else:
    a_list.append(cut_times[1])

a_list.sort()
b_list.sort()

max_width = max(a_list[i] - a_list[i-1] for i in range(1, len(a_list)))
max_height = max(b_list[i] - b_list[i-1] for i in range(1, len(b_list)))

largest =  max_width * max_height

print(largest)