99클럽 코테 스터디 30일차 TIL

오늘의 학습 키워드

• 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS)
• 이진 탐색 (Binary Search)

문제 이해

이 문제는 두 개의 배열이 주어졌을 때, 하나의 배열을 다른 배열의 부분 배열로 만들기 위해 필요한 최소한의 삽입 작업 수를 구하는 문제입니다. 이 문제는 최장 증가 부분 수열 (LIS) 문제와 관련이 있습니다. 주어진 배열 arr에서 target 배열의 원소 순서를 유지하는 가장 긴 부분 수열을 찾고, 그 길이를 기반으로 삽입 작업의 최소 수를 계산합니다.

나의 풀이

package org.example.L_1713;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] target = {5, 1, 3};
        int[] arr = {9, 4, 2, 3, 4};
        System.out.println(minOperations(target, arr));
    }

    public static int minOperations(int[] target, int[] arr) {
        HashMap<Integer, Integer> targetIndex = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            targetIndex.put(target[i], i);
        }

        ArrayList<Integer> targetPositions = new ArrayList<>();
        for (int num : arr) {
            if (targetIndex.containsKey(num)) {
                targetPositions.add(targetIndex.get(num));
            }
        }

        if (targetPositions.isEmpty()) {
            return target.length;
        }

        ArrayList<Integer> lis = new ArrayList<>();
        for (int pos : targetPositions) {
            int idx = Collections.binarySearch(lis, pos);
            if (idx < 0) {
                idx = -(idx + 1);
            }
            if (idx < lis.size()) {
                lis.set(idx, pos);
            } else {
                lis.add(pos);
            }
        }

        int lisLength = lis.size();
        return target.length - lisLength;
    }
}

풀이 설명

1. 목표 배열의 인덱스 맵핑

   • target 배열의 원소들을 인덱스로 매핑하여 HashMap에 저장합니다. 이 맵은 target 배열의 각 원소가 arr 배열에서 나타나는 위치를 추적하는 데 사용됩니다.
   • 예를 들어, target = [5, 1, 3]일 때, targetIndex는 {5: 0, 1: 1, 3: 2}로 저장됩니다.

2. 목표 위치 수집

   • arr 배열의 각 원소를 순회하면서, targetIndex에 해당 원소가 존재하는 경우 해당 원소의 위치를 targetPositions 리스트에 추가합니다.
   • 이는 arr 배열에서 target 배열의 원소 순서를 유지하는 부분 배열을 찾는 과정입니다.

3. 최장 증가 부분 수열 (LIS) 계산

   • targetPositions 리스트에서 최장 증가 부분 수열을 찾습니다. 이를 위해 이진 탐색을 사용하여 LIS 배열을 구성합니다.
   • LIS 배열은 target 배열의 부분 배열 중에서 가장 긴 증가하는 순서의 길이를 저장합니다.

4. 최소 삽입 작업 계산

   • LIS의 길이가 target 배열에서 유지된 순서의 길이입니다. 전체 target 배열에서 이 길이를 빼면, 배열을 완성하기 위해 필요한 최소 삽입 작업 수를 계산할 수 있습니다.

예제 설명

주어진 예제에서:

• target = [5, 1, 3]
• arr = [9, 4, 2, 3, 4]

위 과정에 따라, targetIndex는 {5: 0, 1: 1, 3: 2}가 되고, targetPositions는 [2]가 됩니다. 이 경우 최장 증가 부분 수열의 길이는 1이 되며, 최종적으로 target.length - lisLength = 3 - 1 = 2가 되므로, 최소 삽입 작업 수는 2입니다.