99클럽(2기) 코테 스터디 2일차 TIL # Sorting

프로그래머스 - 최소 직사각형

• 문제: 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 반환하도록 solution 함수를 완성해주세요.
• 제한사항: 
  • sizes의 길이는 1이상 10,000 이하입니다.
    • sizes의 원소는 [w, h] 형식입니다.
    • w는 명함의 가로 길이를 나타냅니다.
    • h는 명함의 세로 길이를 나타냅니다.
    • w와 h는 1이상 1,000 이하인 자연수입니다. 

---

풀이 (시간복잡도: O(n))

 우선 문제를 풀기 쉽게 재구성해본다. sizes의 원소는 가로와 세로로 구성되어있는데, 사실 가로와 세로는 고정된 게 아니다. 직사각형을 90 회전시키면 회전 이전의 가로는 세로가, 회전 이전의 세로는 가로가 되기 때문이다. 결국 모든 직사각형을 눕힌 모양으로 만들거나, 세운 모양으로 만들어 가로의 최대값과 세로의 최대값을 곱하면 된다고 생각했다.

 

1) 모든 직사각형을 세운 모양으로 만들기

 sizes의 원소 size를 sorted() 메소드로 정렬해 size 의 두 요소 중 값이 작은 요소가 첫 번째에, 값이 큰 요소가 두 번째에 오도록 했다. 가로가 짧고 세로가 긴 서있는 직사각형 모양이다. 이 때의 시간복잡도는 O(n)이다. 직사각형을 구성하는 요소는 가로와 세로 2개이므로 2개의 요소를 정렬하는 데에 소요되는 시간복잡도는 O(2log2)이다. 2log2는 상수이므로 결국 O(1)이고, 이를 n번 반복하므로 최종적으로는 O(n)이다.

 

2) 가로의 최대값, 세로의 최대값 곱하기

 size의 첫 번째 요소가 가로, 두 번째 요소가 세로이므로 가로의 최대값은 각 size의 첫 번째 요소들 중에서 최대값을 고르면 되고, 세로의 최대값은 각 size의 두 번째 요소들 중에서 최대값을 고른다. 이 때 가로 최대값, 세로 최대값을 구하는 시간복잡도는 각각 O(n)이다.

 

 가로 최대값을 구하는 경우 n개의 size를 순회하며 각 size의 첫 번째 원소를 추출할 때 O(n), 각 size의 첫 번째 원소 중 최대값을 구할 때 O(n)이다. 이 과정은 순차적으로 일어나므로 두 시간 복잡도를 더해 상수 시간을 생략하면 O(n)이다. 세로 최대값을 구하는 과정도 마찬가지이다. 

 

 마지막으로 가로의 최대값, 세로의 최대값을 곱한 값을 반환한다.

정렬에 대한 시간복잡도는 O(n), 가로 최대값 및 세로 최대값은 O(n), 곱셈은 O(1), 다 더하면 O(n)이다. 

def solution(sizes):
    sorted_sizes = [sorted(size) for size in sizes]
    max_w = max([size[0] for size in sorted_sizes])
    max_h = max([size[1] for size in sorted_sizes])
    return max_w * max_h

 

 

다른 사람의 풀이

 충격적...

사실 정렬할 필요도 없었다. 원소의 최솟값들 중 최대값과 원소의 최대값들 중 최대값을 곱한 값을 반환하면 되는 것이었다. 

def solution:
    return max(max(size) for size in sizes) * max(min(size) for size in sizes)

 

 

느낀점

 문제를 곧이 곧대로 받아들이기보다는 추상화하여 재해석하면 더 쉽게 풀 수 있다는 것을 느꼈다. 가로와 세로는 고정된 것이 아니라는 점을 떠올렸기에 작은 값은 가로로, 큰 값은 세로로 임의로 추정할 수 있었다. 이렇게 해서 가로 값들 중 최대값과 세로 값들 중 최대값을 구하는 문제로 재해석했다. 하지만 가로와 세로에 국한되지 않고, 각 size의 작은 값들 중 최대값과 큰 값들 중 최대값을 구하는 단계까지는 추상화하지 못했다. 이 점에서 문제를 더 간단히 해결할 수 있는 방법을 놓쳤다는 것을 깨달았고 다음번에는 풀이를 하고 한번 더 추상화할 수는 없는지 고민해봐야겠다.

 

 

Timsort 관련 포스트

https://d2.naver.com/helloworld/0315536