알고리즘/99Club

99클럽 코테 스터디 30일차 TIL + 이진 탐색 , 최장 증가 부분 수열 (LIS)

dami97 2024. 8. 20. 22:27
반응형

소개

  • 알고리즘 스터디를 참여하며 작성하는 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의 부분 수열로 만들기 위해 필요한 최소 작업 수를 구하는 문제입니다. 이를 위해 다음과 같은 접근 방법을 사용합니다

  1. 해시맵 사용
    • target 배열의 요소들을 인덱스와 함께 해시맵에 저장합니다. 이렇게 하면 arr 배열을 순회할 때, target 배열에서 해당 요소의 위치를 빠르게 찾을 수 있습니다.
  2. 최장 증가 부분 수열 (LIS)
    • arr 배열을 순회하면서 target 배열의 인덱스를 기준으로 최장 증가 부분 수열(LIS)을 계산합니다. LIS는 현재 arr에서 target의 부분 수열이 되는 가장 긴 배열을 의미합니다.
  3. 결과 계산
    • 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;
    }
}

풀이 설명

  1. 해시맵 초기화
    • target 배열의 각 요소를 인덱스와 함께 해시맵에 저장합니다. 이를 통해 arr 배열에서 target의 위치를 빠르게 참조할 수 있습니다.
  2. 최장 증가 부분 수열 (LIS) 계산을 위한 인덱스 리스트 생성
    • arr 배열을 순회하면서 target 배열의 인덱스를 기반으로 새로운 리스트를 생성합니다. 이 리스트는 arr에서 target의 부분 수열을 나타내는 인덱스들로 구성됩니다.
  3. LIS 길이 계산
    • 생성된 인덱스 리스트에서 최장 증가 부분 수열(LIS)의 길이를 계산합니다. 이를 통해 target 배열을 arr의 부분 수열로 만들기 위해 추가해야 하는 최소 작업 수를 구할 수 있습니다.

 

 

마무리하며

  • 이진 탐색을 사용하여 효율적으로 해결할 수 있었습니다.
  • 최장 증가 부분 수열(LIS)을 구하는 방법을 통해, target 배열을 arr의 부분 수열로 만들기 위한 최소 작업 수를 계산할 수 있었습니다.