오늘의 코테문제

import java.util.*;

class Solution {

  

    public int minOperations(int[] target, int[] arr) {

        // target 배열의 요소가 arr 배열에서 나타나는 순서대로 인덱스 찾기

        Map<Integer, Integer> targetIndexMap = new HashMap<>();

        for (int i = 0; i < target.length; i++) {

            targetIndexMap.put(target[i], i);

        }

  

        // arr 배열에서 target 배열의 요소에 해당하는 인덱스를 추출

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

        for (int num : arr) {

            if (targetIndexMap.containsKey(num)) {

                lisSequence.add(targetIndexMap.get(num));

            }

        }

  

        // lisSequence에 대해 LIS를 구함

        return target.length - lengthOfLIS(lisSequence);

    }

  

    // LIS (Longest Increasing Subsequence) 구하는 함수

    private int lengthOfLIS(List<Integer> nums) {

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

        for (int num : nums) {

            int pos = Collections.binarySearch(lis, num);

            if (pos < 0) {

                pos = -(pos + 1);

            }

            if (pos < lis.size()) {

                lis.set(pos, num);

            } else {

                lis.add(num);

            }

        }

        return lis.size();

    }

}

처음에 그냥 로직?을 짜서 구성했는데 통과하지 못헀었다.

import java.util.*;

class Solution {

    static int chk;
    static int idx;


    public static int find(int x, int[] arr){
        int start = idx;
        int end = arr.length-1;

        while(start<=end){
            int mid = (start+end)/2;//index를 가르킴

            if(arr[mid]< x){
                start =mid+1;
            }
            if(arr[mid] > x){
                end = mid-1;
            }

            if(arr[mid] ==x){
                    idx = mid ++;
                    return 1;
            }

        }
        return 0;
    }

    public int minOperations(int[] target, int[] arr) {
        
        idx=0;
        int answer=0;
        //이분탐색 수행하기
        for(int i=0; i<target.length; i++){
            int x  = find(target[i], arr);
            if(x ==0)answer++;
            System.out.print( x+" ");

        }
        System.out.println();


        return answer;
    }
}

처음에는 시작점의 위치를 변경해가면서 이분탐색을 수행하고 값을 확인했는데 이상한 점은 바로 arr배열에 중복된 값이 있을 경우에 어떻게 처리할 것인지 확인하지 못한것이었다.

이 문제를 해결하기위해서 도움을 조금 받았는데

LIS(Longest Increading Subsequence)

최장 증가 부분 수열이다.

수열에서 가장 긴 증가하는 부분 수열을 구하는 문제를 풀 때 사용하는 개념이다.

REVIEW

챌린저문제는 다양한 알고리즘을 알아야 풀 수 있는 것 같다. 풀면 풀수록 뭔가 내가 알고있는 기본지식으로 풀기가 조금 힘든 느낌? 로직을 짜보긴 하지만 좀 더 섬세하게 고려해보지 못하는 것도 있다. ㅠ 열심히해서 잘해보려고 노력하자!

아! 그리고 우수TIL로 선정되었었다 생각보다 예상치 못한 결과라서 살짝 좋았땅 ㅎㅎㅎ

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL