[2024] Day2. 2610. Convert an Array Into a 2D Array With Conditions

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 2일 (화)
Leetcode daily problem

2610. Convert an Array Into a 2D Array With Conditions

https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions/?envType=daily-question&envId=2024-01-02

Problem

정수 배열 nums이 제공될 때, 다음 조건을 만족하는 정수 원소로 구성된 2D 배열을 만들어서 반환한다.

[조건]

• 2D 배열에는 배열 nums의 요소만 포함되어야함
• 각 행에는 고유한 정수 원소로 구성됨
• 2D 배열의 행은 최소화되어야 함
• 결과를 반환할 때, 답이 여러개 인 경우 하나만 반환함

여기서 2D 배열은 각 행에 서로 다른 수의 요소를 가질 수 있다.

Solution

반환해야 하는 2D 배열을 위해 먼저 빈 리스트를 생성한 후(ans), 주어진 정수 배열의 원소와 원소가 등장한 횟수를 키와 값으로 매핑한다.
해당 매핑한 맵의 등장 횟수를 돌면서, 위에서 할당된 ans의 배열의 행의 수와 비교한다.
만약, 등장한 횟수가 ans의 배열의 행보다 크거나 같다면 해당 원소는 이미 등장했기 때문에 새로운 행을 생성하고, 해당 행에 그 원소를 삽입한다.

Code

from collections import Counter

class Solution:
    def findMatrix(self, nums: list[int]) -> list[list[int]]:
        cnt = Counter(nums)
        ans = []
        for k, v in cnt.items():
            for i in range(v):
                if len(ans) <= i:
                    ans.append([])
                ans[i].append(k)
        return ans

Complexicity

시간 복잡도

위의 코드에서 Counter로 nums의 배열을 한번 순회하므로 O(n),
Counter 객체의 각 항목을 순회하면서 반복하므로 O(m) 여기서 m은 서로 다른 원소의 개수
각 원소에 대해 해당 원소의 개수만큼 반복하므로 O(k)
k : 가장 많이 등장한 원소의 최대 갯수
리스트에 추가하는 작업은 O(1)로
전체 시간 복잡도는 O(n+m*k) 이다.

공간 복잡도
Counter 객체를 저장하는 원소의 개수 O(k)
결과 ans를 저장하는 2차원 배열은 최악의 경우에 k개에 따라 서로 다른 원소에 대해 m 개의 리스트가 생성될 수도 있으므로 O(km) 공간이 필요하다.
따라서 전체 공간 복잡도는 O(k+km)이다.

---

개선

Neetcode 강의를 보고 시간복잡도를 O(n)으로 끝내는 solution을 발견했다.

from collections import defaultdict

nums =  [1,3,4,1,2,3,1]
cnt = defaultdict(int)
ans = []

for n in nums:
    row = cnt[n]
    if len(ans) == row:
        ans.append([])
    ans[row].append(n)
    cnt[n] +=1

ans

먼저 결과값인 ans를 defaultdict의 0으로 초기화되는 정수형 기본값으로 할당한다.
그리고 배열 nums를 한번 순회하면서, ans의 특정 원소 값에 접근하고, 배열의 길이와 해당 원소의 값과 비교하고 추가 및 업데이트 하는 연산을 통해서 O(1)의 시간이 걸리므로 최종 전체 시간 복잡도는 O(n)이다.