[BOJ] 백준 [1365] 꼬인 전깃줄 JAVA

https://www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

문제

풀이

전깃줄이 서로 꼬여야 하지 않아야 하므로 가령 , 4 -> 1 번 전봇대로 가는 선을 제거해야 꼬이지 않는다.

즉 , 반대쪽의 전봇대의 번호가 증가하는 수열의 형태면 꼬이지 않으므로 LIS 알고리즘을 통해 해결해야한다.

 

LIS에 대한 이전 포스팅에서 해결방법이 3가지가 있다고 했는데 , 문제에서 조건을보면 N의 갯수가 10만개가 넘어간다.

N^2 이상의 시간복잡도를 가지는 완전탐색 이나 DP 로는 시간초과가 난다는 것.

https://katastrophe.tistory.com/39

[BOJ] 백준 [11722] 가장 긴 감소하는 부분수열 JAVA

 

따라서 이진탐색을 통해 LIS를 풀어야 한다.

증가하는 수열의 크기를 size 라고 하고 전봇대의 수를 N이라고 하면 N-size 만큼의 전깃줄을 제거해야 꼬이지 않는다.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        List<Integer> list = Arrays.stream(br.readLine().split(" ")).
                mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
        ArrayList<Integer> result = new ArrayList<>();
        result.add(list.get(0));
        for(int i=1;i<N;i++){
            int next = list.get(i);
            if(result.get(result.size()-1) < next)
                result.add(next);
            else{
                int pos = -Collections.binarySearch(result, next)-1;
                result.set(pos,next);
            }
        }
        System.out.println(N-result.size());
    }
}
 

list 에 입력받은 초기 정보를 받은다음에 result에 첫번째 요소를 집어넣은 다음 

list의 1번째 부터 ~ N 번째 까지 순회를하면서 result에 적절히 들어갈 자리를 찾아가면 끝.

(참고로 result에 담긴 수열이 증가하는 수열 그대로 나타낸 것은 아님. 추가로 다른방법으로 해줘야 함)