문제링크: https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions/
1. 문제설명
1.1. 요구사항
정수 배열 nums가 주어지면 다음과 같은 조건을 만족하는 2차원 배열을 만들어라
- 2차원 배열은 오직 nums배열의 요소만을 포함한다.
- 2차원 배열의 각 행은 중복되지 않는 정수로 이루어진다.
- 2차원 배열의 행 개수는 최소가 되어야 한다.
배열을 반환하되, 복수의 정답이 있을 경우 하나만 반환한다.
1.2. 입출력 예시
Example 1:
Input: nums = [1,3,4,1,2,3,1]
Output: [[1,3,4,2],[1,3],[1]]
Example 2:
Input: nums = [1,2,3,4]
Output: [[4,3,2,1]]
1.3. 제한사항
- 1 <= nums.length <= 200
- 1 <= nums[i] <= nums.length
2. 풀이
2.1. 나의 생각
문제를 풀기에 앞서서 문제 해결에 필요한 조건은
- 2차원 배열의 행을 동적으로 생성 하는 것
- 각행에 중복되는 정수가 존재하는 지 확인하는 것
으로 생각했습니다.
사이트에서 반환값으로 List<List>를 제시한 것으로 보아 Collection을 활용하는 것을 고려했고 List에서 제공하는 contains()함수로 중복확인은 쉽게 해결하였습니다.
다음은 행을 동적으로 생성하는 것인데 이 로직을 구현하는 방법이 이 문제의 핵심인 것 같습니다.
제가 생각한 로직은
- nums에서 정수를 읽어들인다.
- 순차적으로 행을 순회한다.
- 정수가 중복되지 않는 행에 도달하면 정수를 행에 추가한다.
- 모든 행을 순회할 때 까지 정수가 중복되면 새로운 행을 동적으로 추가한다.
입니다.
그렇게 구현한 코드가 이렇게 나옵니다
class Solution {
public List<List<Integer>> findMatrix(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
ans.add(new ArrayList<>());
boolean done = false;
for(int i : nums){
done = false;
for(List l : ans){
if(!l.contains(i)){
l.add(i);
done = true;
break;
}
}
if(!done){
ans.add(new ArrayList<>(Arrays.asList(i)));
}
}
return ans;
}
}현제 존재하는 모든행을 순회해도 추가를 하지 못하는 경우를 확인하기 위해서 boolean값을 하나 추가해 주었습니다.
2.2. 결과
테스트케이스들을 모두 통과 했지만 런타임과 메모리 모두 하위권에 속하네요.
2.3. 비교
class Solution {
public List<List<Integer>> findMatrix(int[] num) {
List <Integer> nums = new ArrayList<>();
for(int i=0;i<num.length;i++){
nums.add(num[i]);
}
List <List<Integer>> list = new ArrayList<>();
while(nums.size() > 0){
List <Integer> l2 = new ArrayList<>();
int i = 0;
while(i < nums.size()){
if(!l2.contains(nums.get(i))){
l2.add(nums.get(i));
nums.remove(i);
}
else{i++;}
}
list.add(l2);
}
return list;
}
}런타임 성능이 더 뛰어난 다른분의 코드를 보니 입력 받은 정수 배열을 여러번 순회하여 중복되지 않게 한 행을 만들고 추가하는 식으로 코드를 구성하고, 추가된 정수는 삭제하여 순회할 배열의 크기를 줄여나가 셨네요.
저는 중복된 정수가 많아질 수록 순회해야하는 리스트의 개수가 늘어나는 부분이 성능저하를 많이 일으킨거 같습니다.
3. 후기
문제를 해결하는 방법을 어떻게 접근하냐에 따라서 성능이 극단적으로 갈리네요. 지금까지는 문제만 풀면 그만이라는 생각으로 해결되면 넘겼던 문제들이 많은데 이렇게 글을 쓰면서 개선했어야 할 부분을 직접 찾아서 고민하고 생각을 해보는 시간을 가지니 이번에 배운 점들은 기억에 남을 것 같습니다.
