99클럽 코테 스터디 30일차 TIL / [LeetCode] Minimum Operations to Make a Subsequence

오늘의 학습 키워드

---

이분탐색, LIS

문제

---

https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/description/

• 플랫폼: LeetCode
• 문제명: Minimum Operations to Make a Subsequence
• 난이도: Hard

풀이

---

class Solution {
	public int minOperations(int[] target, int[] arr) {
        // target 배열의 인덱스와 값을 바꾸어 저장 (key: target 값, value: 인덱스)
		Map<Integer, Integer> map = new HashMap<>();

		for(int i = 0; i < target.length; i++) {
			map.put(target[i], i);
		}

		List<Integer> idxArr = new ArrayList<>();

		for(int i = 0; i < arr.length; i++) {
			if(!map.containsKey(arr[i])) {
				continue;
			}

			idxArr.add(map.get(arr[i]));
		}

		int[] lis = new int[target.length];
    int lisLength = 0;

    if(!idxArr.isEmpty()) {
        lis[0] = idxArr.get(0);
        lisLength = 1;

        for(int i=1; i<idxArr.size(); i++) {
            // 마지막에 삽입
            if(lis[lisLength - 1] < idxArr.get(i)) {
                lis[lisLength++] = idxArr.get(i);
            }
            // 중간에 삽입
            else {
                int index = binarySearch(lis, lisLength, idxArr.get(i));
                lis[index] = idxArr.get(i);
            }
        }
    }

		return target.length - lisLength;
	}

	public int binarySearch(int[] lis, int lisLength, int targetIdx) {
		int left = 0;
        int right = lisLength - 1;

		while(left < right) {
			int mid = left + (right - left) / 2;

			if(lis[mid] >= targetIdx) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return right;
	}
}

접근

• lis의 길이를 구하여, target 배열 사이즈에서 빼주어 정답을 도출했습니다.
• lis 구현 방식에는 DP를 활용한 방법, 이분탐색을 활용한 방법이 있습니다.
  • DP → O(n^2)의 시간 복잡도를 가지므로, 배열의 크기가 최대 10^5인 해당 문제에서는 시간 초과가 발생하게 됩니다.
  • 이분탐색 → O(nlogn)의 시간 복잡도를 가지므로 시간 내에 풀이가 가능합니다.

구현

• target 배열의 값으로 인덱스를 바로 조회할 수 있게 map을 사용했습니다.

  // target 배열의 인덱스와 값을 바꾸어 저장 (key: target 값, value: 인덱스)
  Map<Integer, Integer> map = new HashMap<>();
  
  for(int i = 0; i < target.length; i++) {
  	map.put(target[i], i);
  }

• 이 문제에서는 인덱스의 순서를 기준으로 lis를 구해야 합니다. 따라서, 입력 배열 arr에서 target에 속하는 값들만 추출한 뒤, 해당 값에 대한 target에서의 인덱스를 idxArr에 저장했습니다.

  List<Integer> idxArr = new ArrayList<>();
  
  for(int i = 0; i < arr.length; i++) {
  	if(!map.containsKey(arr[i])) {
  		continue;
  	}
  
  	idxArr.add(map.get(arr[i]));
  }

• idxArr를 순회하며, 마지막에 삽입할 수 있는 경우 → 바로 삽입, 중간에 삽입해야 하는 경우 → 이분탐색을 통해 삽입 위치를 찾아 삽입합니다.

  if(!idxArr.isEmpty()) {
      lis[0] = idxArr.get(0);
      lisLength = 1;
  
      for(int i=1; i<idxArr.size(); i++) {
          // 마지막에 삽입
          if(lis[lisLength - 1] < idxArr.get(i)) {
              lis[lisLength++] = idxArr.get(i);
          }
          // 중간에 삽입
          else {
              int index = binarySearch(lis, lisLength, idxArr.get(i));
              lis[index] = idxArr.get(i);
          }
      }
  }

• 최종적으로 구해진 lis의 길이를 target 배열의 길이에서 빼주어 정답을 도출합니다.

소요 시간

2시간