[문제 이름 : Maximum Operations to make a Subsequence (리트코드, Hard)]
문제 url : https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/description/
내가 작성한 코드는 아래와 같다.
import java.util.*;
class Solution {
public int minOperations(int[] target, int[] arr) {
// key: target의 값, value: target의 인덱스 (target값은 중복값이 없으므로)
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<target.length; i++) {
map.put(target[i], i);
}
// arr 배열에서 target 원소들의 인덱스 리스트 생성
List<Integer> indexList = new ArrayList<>();
for(int num : arr) {
if(map.containsKey(num)) {
indexList.add(map.get(num));
}
}
// indexList에서 LIS 구하기
List<Integer> lis = new ArrayList<>();
for(int index : indexList) {
// 현재 index가 lis에 들어갈 위치를 찾기 위해 binarySearch로 탐색
int pos = binarySearch(lis, index);
if(pos < lis.size()) {
// lis의 pos 위치를 현재 index로 대체
lis.set(pos, index);
} else {
// pos가 lis의 크기와 같다면 새로운 원소를 리스트에 추가
lis.add(index);
}
}
// target 배열의 전체 길이에서, LIS의 길이를 뺀 값이 최소 삽입 연산의 수
return target.length - lis.size();
}
// list 내에서 key가 삽입될 위치를 찾는다.
static int binarySearch(List<Integer> list, int key) {
int start = 0;
int end = list.size() - 1;
while(start <= end) {
int mid = (start + end) / 2;
// 중간 위치의 값이 key보다 작은 경우
if(list.get(mid) < key) {
start = mid+1;
} else {
end = mid-1;
}
}
return start;
}
}
[풀이 과정]
target 배열이 arr 배열의 서브시퀀스(LIS)가 되기 위해 필요한 최소한의 삽입 연산수를 찾는 문제이다.
서브시퀀스(LIS)는 원래 배열의 순서를 유지하며, 일부 원소를 제거하여 만들 수 있는 배열을 의미한다.
1. target 배열의 각 원소가 arr 배열에서 몇 번째 위치에 있는지를 찾고, Map에 저장한다.
2. arr 배열을 순회하며, Map에 존재하는 원소를 찾는다. 해당 원소가 map에 존재하면, indexList에 추가해준다. 이는 arr 배열에서 target 배열에 있는 요소들의 인덱스 순서를 기록한 리스트를 생성하기 위함이다.
3. binarySearch 메소드를 사용하여 리스트 내에서 key가 들어갈 위치를 찾는다. start값은 key를 삽입할 위치가 되며, lis 리스트의 값을 대체하거나 새로 추가하는 데 사용된다.
4. indexList 리스트를 통해, 최장 증가 부분 수열을 구한다. 최종적으로 LIS를 구한 이후, 최소 삽입 연산의 수는 target 배열의 길이에서, LIS의 길이를 뺀 값이므로 이를 리턴한다.
풀다가 도저히 구현 방법이 떠오르지 않아, 다른 사람이 풀이한 코드를 참고하였다.
풀이 시간 : 2시간 30분