탭고리즘 2024-12-20 숫자 카드 게임

 

 

• 문제설명
  숫자 N을 입력받은 후 다음 입력으로 N만큼의 숫자를 입력받는다. 이 입력받은 여러 개의 숫자를 오름차순으로 정렬상태로 만들어야 한다. 이때 최소한의 카드만을 제거해야 하는데 이때 최소 카드 수를 출력하면 된다. 

• 제출코드     

import java.util.*;
import java.io.*;

public class CardSorting {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] cards = new int[N];
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(minRemovalsToSort(N, cards));
    }

    public static int minRemovalsToSort(int n, int[] cards) {
        ArrayList<Integer> lis = new ArrayList<>();
        for (int card : cards) {
            int pos = Collections.binarySearch(lis, card);
            if (pos < 0) pos = -(pos + 1); // 위치 조정
            if (pos == lis.size()) {
                lis.add(card);
            } else {
                lis.set(pos, card); // 값 갱신
            }
        }
        return n - lis.size(); // 최소 제거 카드 수 계산
    }
}

 

코드설명
메인 함수에서는 숫자들을 입력받고 실제 로직 함수를 출력하는 역할만을 한다. 그럼 minRemovalsToSort함수를 알아보겠다.
먼저 ArrayList lis를 하나 만들어 준다음 카드 리스트에서 for문을 돈다.
카드 리스르를 돌면서 조건에 해당하는 카드들을 ArrayList에 추가해 줄 것이다. 이때 사용하는 함수가 Collections의 binarySearch함수이다. 일단 이 함수를 쓰기 위해서는 먼저 정렬된 상태에서 진행해야 한다.
다음 예시 코드를 살펴보겠다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);
        int index = Collections.binarySearch(list, 5);
        System.out.println(index); // 출력: 2 (5의 인덱스)
    }
}

먼저 이 함수의 첫번째 인자로는 리스트, 두 번째 인자로는 위치를 찾고 싶은 숫자이다. 위는 찾고자 하는 숫자가 리스트에 존재하는 경우이다. 이를 통해 해당 숫자의 인덱스를 알 수 있다. 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);
        int index = Collections.binarySearch(list, 6);
        System.out.println(index); // 출력: -4 (삽입 위치는 3)
    }
}

 

위는 찾고자 싶은 숫자가 리스트에 없는 경우이다. 이와 같은 경우에는 다음과 같이 동작한다.

 

위와 같이 동작하기 때문에 위 코드에서는 index에 -4가 저장되게 된다. 
index에는 -4가 저장되지만 만약 6을 기존의 리스트에 추가해야 한다면 -(index + 1)을 통해 추가해야 할 인덱스를 알 수 있다.

Collections.binarySearch는 Longest Increasing Subsequence에서 많이 사용된다. 최고 증가수열을 구하는 문제이다.
이진 탐색을 사용하여 삽입 위치를 효율 적으로 찾아서 문제를 풀 수 있다. 

 

public static int minRemovalsToSort(int n, int[] cards) {
        ArrayList<Integer> lis = new ArrayList <>();
        for (int card : cards) {
            int pos = Collections.binarySearch(lis, card);
            if (pos < 0) pos = -(pos + 1); // 위치 조정
            if (pos == lis.size()) {
                lis.add(card);
            } else {
                lis.set(pos, card); // 값 경신
            }
        }
        return n - lis.size(); // 최소 제거 카드 수 계산
    }

 

그럼 코드를 살펴보면 위치 조정까지 이루어진 상태이다. 

계산한 위치가 리스트의 크기와 같다면 리스트 마지막에 추가해 주면 된다.
만약 아니라면 pos의 값을 card값으로 경신해 준다.
전체 N에서 리스트의 크기만 빼서 최소 제거 카드 수를 구해 반환해 준다.