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

https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions/description/

Convert an Array Into a 2D Array With Conditions - LeetCode

leetcode - Convert an Array Into a 2D Array With Conditions

문제 유형 : 해시, 행렬, 그리디

문제 난이도 : Medium

 

문제

You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:

• The 2D array should contain only the elements of the array nums.
• Each row in the 2D array contains distinct integers.
• The number of rows in the 2D array should be minimal.

Return the resulting array. If there are multiple answers, return any of them.

Note that the 2D array can have a different number of elements on each row.

 

당신은 정수 배열 nums를 받는다. 2차원 배열을 아래 규칙에 따라 만들어야 한다.

• 2차원배열은 nums의 요소를 하나씩만 사용해서 만들어야한다
• 각 열은 서로 다른 정수를 담을 수 있다.
• 열의 수는 최소 개수여야 한다.

결과를 반환하시오. 중복 답안이 있을 수 있습니다.

2차원배열이 각각 다른 열에서 다른 개수를 가져도 된다는 것을 참고하시오.

 

 

풀이

이 문제의 핵심은, 매 열마다 최대한 많은 요소들을 넣어야 한다는 것이다.

 

map을 생성하여 정수-남은정수의개수 형태로 만든다.

배열을 1회 순회하여 해시 테이블의 값을 각각 추가시킨다.

 

map의 각 요소를 하나씩 꺼내어서 임시배열에 값을 넣는다.

그 뒤, 그 요소의 개수를 1 줄인다.

만약 남은 개수가 0이라면, map에 그 키-값쌍을 없앤다.

아니라면, 다음 키-값쌍으로 넘어간다.

Iterator를 이용하면 되겠다.

임시 배열을 행렬에 추가한다.

이 과정을 해시 테이블에 값이 있는 동안 계속한다.

 

큐를 이용한 다른 풀이도 있다.

큐에 모든 요소를 넣는다.

만약 임시 배열에 큐의 맨 앞 값이 없다면, 큐에서 pop하여 배열에 넣는다.

만약 임시 배열에 이미 값이 있다면, 큐에서 pop한 값을 다시 push한다.

이 과정을 처음 큐의 크기만큼 하면, 한 바퀴를 돈다.

임시 배열을 행렬에 추가하고, 큐가 빌 때까지 이 과정을 반복하면 된다.

 

 

코드

C++

 

풀이 - 해시를 이용한 풀이

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        unordered_map<int, int> mp;
        vector<vector<int>> mat;

        for(const auto &num : nums) {
            mp[num]++;
        }

        while(!mp.empty()) {
            vector<int> tmpArr;
            for(auto it = mp.begin(); it != mp.end(); ) {
                tmpArr.push_back(it -> first);
                it -> second--;
                if(it -> second == 0) {
                // erase후, 다음 iterator로 자동으로 넘어감
                    it = mp.erase(it);
                } else {
                // 다음 iterator로 넘어감
                    ++it;
                }
            }
            // 임시 배열을 행렬에 추가
            mat.push_back(tmpArr);
        }

        return mat;
    }
};

 

 

풀이 - 큐를 이용한 풀이

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        queue<int> q;
        vector<vector<int>> mat;

        for(const auto &num : nums) {
            q.push(num);
        }

        while(!q.empty()) {
            int qSize = q.size();
            unordered_map<int,int> um;
            vector<int> tmpArr;
            for(int i = 0; i < qSize; i++) {
                if(!um[q.front()]) {
                    um[q.front()]++;
                    tmpArr.push_back(q.front());
                    q.pop();
                } else {
                    q.push(q.front());
                    q.pop();
                }
            }
            mat.push_back(tmpArr);
        }

        return mat;
    }
};

 

 

hash table

<컴퓨터>해시표(~表)