[Java] Daily LeetCode Challenge 1035. Uncrossed Lines

https://leetcode.com/problems/uncrossed-lines/

Uncrossed Lines - LeetCode

 

내 코드 설계의 문제점을 한 번 더 되짚어준 문제

 

연결된 모든 선을 인덱스 기준으로 정렬해서 DP로 풀었다!

 

방법은 다음과 같다

1. HashMap<Integer, HashSet<Integer>> 이용해서, nums2의 값과 위치(HashSet)를 저장한다.

2. nums1의 값을 이용해 HM의 위치 인덱스들을 가져온다 (없으면 빈 List 가져옴)

3. 모든 선을 ArrayList에 저장하고, 첫번째 인덱스가 작은순 > 두번째 인덱스가 작은 순으로 정렬한다.

4. 모든 선을 탐색하되, 첫번째 두번째 인덱스 모두가 작은 경우의 dp값 + 1을 적용해준다.

(없으면 1개로 지정해줌 - 해당 선이 첫번째로 선택된 경우를 의미)

 

마지막 dp값이 최댓값이라는 보장이 없기 때문에 그때그때 max값을 비교해서 답으로 지정해준다.

 

 

[코드]

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length, ans = 0;
        
        ArrayList<int[]> arr = new ArrayList<>();

        HashMap<Integer, HashSet<Integer>> hm = new HashMap<>();
        for(int i=0; i<n2; i++){
            int num = nums2[i];
            HashSet<Integer> hs = hm.getOrDefault(num, new HashSet<>());
            hs.add(i);
            hm.put(num, hs);
        }

        for(int i=0; i<n1; i++){
            int num = nums1[i];
            for(int j : hm.getOrDefault(num, new HashSet<>())){
                arr.add(new int[] {i, j});
            }
        }

        Collections.sort(arr, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                if(o1[0]==o2[0])
                    return o1[1]-o2[1];
                return o1[0]-o2[0];
            }
        });

        int N = arr.size();
        int[] dp = new int[N];

        for(int i=0; i<N; i++){
            int[] now = arr.get(i);
            dp[i]=1; 

            for(int j=i-1; j>=0; j--){
                int[] prev = arr.get(j);

                if(now[0] > prev[0] && now[1] > prev[1]){
                    dp[i]=Math.max(dp[i], dp[j]+1);
                }
            }
            ans = Math.max(dp[i], ans);
        }

        return ans;
    }
}