반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- LeetCode - Minimum Operations to Make a Subsequence (문제 링크)
- 이진 탐색 (Binary Search)
- 최장 증가 부분 수열 (LIS)
문제 설명
주어진 target 배열은 중복되지 않은 정수들로 구성되어 있으며, 다른 배열 arr은 중복된 정수를 가질 수 있습니다. target 배열을 arr의 부분 수열로 만들기 위해 필요한 최소 작업 수를 구하는 문제입니다.
하나의 작업은 arr의 임의의 위치에 새로운 정수를 삽입하는 것입니다. 이때, 삽입할 수 있는 정수는 target 배열에 있는 값만 가능합니다.
부분 수열은 원래 배열에서 일부 요소를 제거하면서 그 순서를 유지하는 배열입니다.
입출력 예시
예제 1
Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: 5와 1을 추가하면 arr은 [5,9,4,1,2,3,4]가 되며, 이때 target이 arr의 부분 수열이 됩니다.
예제 2
Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3
문제 접근
이 문제는 target 배열을 arr의 부분 수열로 만들기 위해 필요한 최소 작업 수를 구하는 문제입니다. 이를 위해 다음과 같은 접근 방법을 사용합니다
- 해시맵 사용
- target 배열의 요소들을 인덱스와 함께 해시맵에 저장합니다. 이렇게 하면 arr 배열을 순회할 때, target 배열에서 해당 요소의 위치를 빠르게 찾을 수 있습니다.
- 최장 증가 부분 수열 (LIS)
- arr 배열을 순회하면서 target 배열의 인덱스를 기준으로 최장 증가 부분 수열(LIS)을 계산합니다. LIS는 현재 arr에서 target의 부분 수열이 되는 가장 긴 배열을 의미합니다.
- 결과 계산
- target 배열의 길이에서 LIS의 길이를 빼면, target 배열을 arr의 부분 수열로 만들기 위해 추가해야 하는 최소 작업 수가 됩니다.
풀이 - Java 코드
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public int minOperations(int[] target, int[] arr) {
// 1. 해시맵 초기화
Map<Integer, Integer> targetIndexMap = new HashMap<>();
for (int i = 0; i < target.length; i++) {
targetIndexMap.put(target[i], i);
}
// 2. 최장 증가 부분 수열 (LIS) 계산을 위한 인덱스 리스트 생성
List<Integer> targetIndices = new ArrayList<>();
for (int num : arr) {
if (targetIndexMap.containsKey(num)) {
targetIndices.add(targetIndexMap.get(num));
}
}
// 3. LIS 길이 계산
return target.length - lengthOfLIS(targetIndices);
}
private int lengthOfLIS(List<Integer> nums) {
List<Integer> lis = new ArrayList<>();
for (int num : nums) {
int pos = binarySearch(lis, num);
if (pos == lis.size()) {
lis.add(num);
} else {
lis.set(pos, num);
}
}
return lis.size();
}
private int binarySearch(List<Integer> lis, int target) {
int left = 0, right = lis.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (lis.get(mid) == target) {
return mid;
} else if (lis.get(mid) < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
풀이 설명
- 해시맵 초기화
- target 배열의 각 요소를 인덱스와 함께 해시맵에 저장합니다. 이를 통해 arr 배열에서 target의 위치를 빠르게 참조할 수 있습니다.
- 최장 증가 부분 수열 (LIS) 계산을 위한 인덱스 리스트 생성
- arr 배열을 순회하면서 target 배열의 인덱스를 기반으로 새로운 리스트를 생성합니다. 이 리스트는 arr에서 target의 부분 수열을 나타내는 인덱스들로 구성됩니다.
- LIS 길이 계산
- 생성된 인덱스 리스트에서 최장 증가 부분 수열(LIS)의 길이를 계산합니다. 이를 통해 target 배열을 arr의 부분 수열로 만들기 위해 추가해야 하는 최소 작업 수를 구할 수 있습니다.
마무리하며
- 이진 탐색을 사용하여 효율적으로 해결할 수 있었습니다.
- 최장 증가 부분 수열(LIS)을 구하는 방법을 통해, target 배열을 arr의 부분 수열로 만들기 위한 최소 작업 수를 계산할 수 있었습니다.
반응형