99클럽 코테 스터디 30일차 TIL + Minimum Operations to Make a Subsequence (java)

 

💡 문제

• Minimum Operations to Make a Subsequence
• https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/

권장 시간

• 1시간 30분

소요 시간

• 1시간 30분 + a

 

나의 풀이 코드

import java.util.*;

class Solution {
    public int minOperations(int[] target, int[] arr) {
        // target의 위치 저장
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            map.put(target[i], i);
        }

        // arr에서 target에 존재하는 값들의 위치 저장
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                list.add(map.get(num));
            }
        }

        return target.length - lis(list);
    }

    // 최장 증가 부분 수열 (LIS)
    private int lis(List<Integer> list) {
        List<Integer> lis = new ArrayList<>();
        for (int l : list) {
            int idx = Collections.binarySearch(lis, l);
            if (idx < 0) {
                idx = -(idx + 1);
            }
            if (idx >= lis.size()) {
                lis.add(l);
            } else {
                lis.set(idx, l);
            }
        }
        return lis.size();
    }
}