[BOJ - JAVA] 1365 - 꼬인 전깃줄(이분탐색, 가장 긴 증가하는 부분수열)

# 주소

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

1365번: 꼬인 전깃줄

 

# 문제

 

# 문제 해설 및 코드 리뷰

 

import java.util.*; 
import java.io.*;
public class Main { 
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String args[]) throws IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        int n = Integer.parseInt(br.readLine()); 
        String str[] = br.readLine().split(" "); 
        int arr[] = new int[n]; 
        arr[0] = Integer.parseInt(str[0]); 
        int size = 1; 
        for (int i = 1; i < n; i++) { 
            int h = Integer.parseInt(str[i]); 
            if (arr[size - 1] < h) 
                arr[size++] = h; 
            else { 
                int left = 0; 
                int right= size; 
                int mid = 0; 
                while (left < right) { 
                    mid = (left + right) / 2; 
                    if (arr[mid] < h) left = mid + 1; 
                    else right = mid; 
                } 
                arr[right] = h; 
            } 
        } 
        bw.write(String.valueOf(n-size)); 
        bw.flush(); 
    } 
}

가장 긴 증가하는 부분 수열2 문제와 너무나도 똑같았습니다. 

이 문제도 마찬가지로 이분 탐색으로 풀어야 합니다. 이분 탐색 시리즈는 

https://codingrapper.tistory.com/52

12015 - 가장 긴 증가하는 부분 수열2(이분 탐색)

이곳에서 자세하게 알아볼 수 있으니 참고해주시기 바라겠습니다.

 

이 문제도 마찬가지로 증가하는 값이면 arr에 담고 그렇지 않으면 이분탐색을 실행합니다.

이 때, left와 mid, right값을 설정할 필요가 있습니다. left = 0, mid = left + right / 2, right = size로 설정합니다.

그리고 while(left < right)일 때 만약 arr[mid]값이 입력받은 h 보다 작으면 arr[mid]의 인덱스보다 작은 값들은 모두 탐색할 필요가 없는 값들이기 때문에 left 값이 0이었던 것을 mid + 1로 바꾸어 줍니다.

그리고 반대의 경우엔 right 값을 mid로 바꿉니다. 이로 인해 arr[mid]값이 더 크다는 뜻이므로 mid라는 인덱스보다 더 큰 위치의 인덱스들은 탐색할 필요가 없으므로 마찬가지로 mid = right로 바꾸어서 while문을 계속 실행합니다. 

그리고 우리가 찾던  arr[right]에 h를 넣음으로써 size의 크기를 늘리지 않고 arr에 값을 계속해서 담을 수 있습니다.

 

이것을 size만 출력하게 되면 3이 나옵니다. 왜냐하면 증가하는 부분 수열이기 때문에 우리가 찾을 2 3 4만 size에 포함됩니다. 여기서 1은 arr[0]의 자리로 들어가게 되는데, size에는 포함되지 않으므로!! 원하는 출력값을 얻으려고 할 땐 n - size를 해주어야 원하는 답을 얻을 수 있습니다.

 

여기서 의문이 드실 수 있습니다. '꼬인 전깃줄'문제인데 왜 증가하는 부분수열 개념이 들어가는지를요.

잘 생각해 봅시다. 우리가 여기서 생각해야할 부분은 꼬여있는 전깃줄이 몇개인지를 파악하는 것이 중요합니다. 즉, 대부분의 입력값은 단조 증가한다고 할 때 몇 개의 입력값 때문에 전부 다 증가하는 것이 아니므로 증가하지 않는 값들을 찾아서(같은경우엔 됩니다) 그 경우들을 출력하면 됩니다.

마찬가지로 증가하는 부분수열의 인덱스를 구한 뒤, 전체 n에서 빼면 원하는 답이 되실거니다.

감사합니다.