[Python][백준 BOJ Silver V] 2628. 종이 자르기 : 정렬, 리스트 컴프리헨션을 활용한 출력

접근 방식

접근을 어떻게 해야 할지 아이디어를 떠올리는데 꽤나 걸렸다. 핵심은 정렬!!

 

1. 가장 큰 종이 조각의 넓이를 출력하려면, 어떤 식으로 잘린 상태인지 알아야 한다.
2. 가로 세로 각각 가장 긴 길이를 가진 사각형이 가장 큰 넓이를 가진 사각형!
3. 따라서 사각형이 가질 수 있는 가로와 세로 길이를 알아야 한다.
4. 우선 가로, 세로 잘린 점들을 넣을 배열을 각각 선언하고
5. 가로 세로 입력값과, 원래 직사각형의 가로 세로 원점과 끝점을 선언한 배열에 각각 넣는다.
6. 그 후 정렬을 하면
7. 각 배열에서 element와 다음(또는 이전) element의 차를 이용해 길이를 구할 수 있다.
8. 가장 큰 가로/세로 길이를 곱해 출력한다.

잘린 사각형들의 가로/세로 길이를 구하기 위해서는 정렬을 해야 한다. ⭐

세로 배열에는 입력값인 3, 2와 본래 직사각형의 세로 길이인 8, 원점인 0이 들어있다. (처음엔 [0, 8, 3, 2] 상태)

직사각형들의 세로 길이인 2, 1, 5(그림 참고)를 구하려면 배열이 정렬된 상태([0, 2, 3, 8])에서 나란히 있는 element들의 차를 이용하면 편하다.

 

구현할 때 출력 부분이 내가 느끼기엔 까다로워서 어떻게 깔끔하게 작성할 수 있을지에 대한 고민이 많았는데,
리스트 컴프리헨션을 출력할 때도 사용할 수 있다는 걸 알게 되었다.

✅ Solution 1 - 출력 시 리스트 컴프리헨션 사용

import sys
w, h = map(int, sys.stdin.readline().split())
width = [0, w]  # 원점, 끝점
height = [0, h] # 원점, 끝점

n = int(sys.stdin.readline())   # 점선 개수
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a == 0:
        height.append(b)
    else:
        width.append(b)

height.sort()
width.sort()

print(
    max([width[i] - width[i - 1] for i in range(1, len(width))])
    *
    max([height[i] - height[i - 1] for i in range(1, len(height))])
)

원래는 아래처럼 작성하려고 했다.

w_list = [width[i] - width[i - 1] for i in range(1, len(width))]
h_list =  [height[i] - height[i - 1] for i in range(1, len(height))]

print(max(w_list) * max(h_list))

그러나 print()문 내에서도 리스트 컴프리헨션을 이용할 수 있다는 걸 알게되었다. 변수명 작성 안해도 되서 맘에 든다 ㅎ

✅ Solution 2 - 리스트 컴프리헨션 사용 X

import sys
w, h = map(int, sys.stdin.readline().split())
width = [0, w]  # 원점, 끝점
height = [0, h] # 원점, 끝점

n = int(sys.stdin.readline())   # 점선 개수
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a == 0:
        height.append(b)
    else:
        width.append(b)

height.sort()
width.sort()

h_list = []
w_list = []
for i in range(1, len(height)):
    x = height[i] - height[i-1]
    h_list.append(x)
for j in range(1, len(width)):
    y = width[j] - width[j-1]
    w_list.append(y)
print(max(h_list)*max(w_list))

리스트 컴프리헨션은 리스트 초기화부터 원소 삽입까지 한번에 할 수 있다.

리스트 컴프리헨션을 사용하지 않고 Solution 1의 로직으로 구현하려면 우선 두개의 리스트를 초기화하고(h_list, w_list) for문을 돌면서 원소를 하나씩 삽입해준다. 이후 각 리스트의 최댓값끼리 곱하면 가장 큰 넓이를 구할 수 있다.

리스트 컴프리헨션을 사용하지 않으니 코드가 좀 더 지저분하게 느껴진다.

✳️ Solution 3 - 새롭게 알게된 방식 (이중 for문 내에서 최댓값 찾기)

import sys
w, h = map(int, sys.stdin.readline().split())
width = [0, w]  # 원점, 끝점
height = [0, h] # 원점, 끝점

n = int(sys.stdin.readline())   # 점선 개수
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a == 0:
        height.append(b)
    else:
        width.append(b)

height.sort()
width.sort()

max_area = 0
for i in range(1, len(height)):
    for j in range(1, len(width)):
        x = height[i] - height[i-1]
        y = width[j] - width[j-1]
        max_area = max(x*y, max_area)
print(max_area)

다른 방식을 알게되어 코드를 작성해보았다.

이중 for문으로 넓이의 모든 경우의 수를 구하고, max()를 이용해 max_area의 기존 값과 비교해 해당 루프에서의 x*y가 더 크다면 max_area의 값을 바꾸어준다.

즉, for문이 도는 동안 max_area의 값은 계속해서 최대값으로 갱신될 것이다.

 

---

💭 What I Learned

1. 이런 유형의 문제를 풀 때 정렬을 사용한다.
2. 출력할 때도 리스트 컴프리헨션을 활용할 수 있다.

---

https://www.acmicpc.net/problem/2628

2628번: 종이자르기