1 분 소요

문제

문제 바로가기

입력

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력

첫째 줄에 최대 연결 개수를 출력한다.

접근방법

 가장 긴 증가하는 부분수열(Longest Increasing Subsequence)을 구하는 문제다.

11053번 가장 긴 증가하는 부분수열에서도 다룬 적이 있다.

하지만 저번 문제에서는 동적계획법을 활용해서 풀었다면, 이번 문제에서는 이진탐색을 이용해 해결했다.

참고로, 동적계획법 풀이는 O(n^2)의 시간복잡도를, 이분탐색을 활용한 풀이는 O(nlog n)의 시간복잡도를 가진다.

 우선, arr배열을 탐색하면서 각 요소가 LIS를 만들 수 있는지를 검사한다. 여기서 dp배열에 채워진 길이는 arr배열에서의 해당 위치에서 가질 수 있는 LIS의 길이를 의미한다.

만약 배열의 값이 현재까지 구한 dp배열의 모든 요소보다 크다면 dp배열의 마지막에 위치하게 되고, dp배열에 채워진 요소 중 하나보다 작다면 dp배열에 해당 요소가 들어갈 자리를 이진탐색을 통해 찾고 그 자리에 삽입한다.

arr배열의 모든 요소가 탐색이 끝나면 dp배열의 길이를 통해 LIS의 길이를 구할 수 있다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int lis = 0;
        for(int i = 0; i < n; i++) {
            int index = binarySearch(arr[i], 0, lis, lis+1);
            if(index == -1) {
                dp[lis++] = arr[i];
            }
            else {
                dp[index] = arr[i];
            }
        }

        System.out.println(lis);
    }

    public static int binarySearch(int num, int left, int right, int size) {
        int res = 0;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(num <= dp[mid]) {
                res = mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        if(left == size) {
            return -1;
        }
        else {
            return res;
        }
    }
}

댓글남기기

참고