백준 2352 반도체 설계 Java

 

그리디 문제를 풀다가 만난 반도체 설계 문제인데

그리디적으로 풀려고 노력하다 실패하고 인터넷을 찾아봐도

그리디 알고리즘으로 푼 자료를 찾지 못해서 LIS(가장 긴 증가하는 부분 수열) 알고리즘으로

풀고 정리하려 한다.

 

하지만 저번에 정리했던 LIS알고리즘으로는 이 문제를 풀 수가 없다.

https://dundung.tistory.com/18?category=744408

백준 11053 가장 긴 증가하는 부분 수열 Java

이 알고리즘은 시간 복잡도가 O(n^2)으로 위 문제에 적용하면 바로 시간 초과가 나오게 된다.

그래서 열심히 찾아본 결과 LIS알고리즘 중에 시간 복잡도 O(nlogn)인 알고리즘이 있어서

공부 후 적용해 본 결과 성공했다.

 

이 문제를 바로 보고 LIS를 떠올리지 못했다. 앞으로는 기억하고 비슷한 문제를 LIS로 풀도록 해야겠다.

비슷한 문제들

• https://www.acmicpc.net/problem/2631
• https://www.acmicpc.net/problem/2532
• https://www.acmicpc.net/problem/2565

O(nlogn)인 LIS 알고리즘은 입력받은 배열 a와 똑같은 길이의 tailTable이라는 배열을 만든다.

tailTable[0] = a[0] 으로 초기화 해준후

증가하는 부분 수열의 길이를 체크할 변수를 하나 만든다

-> tailTable[0]에 a[0] 값이 들어갔으므로 int length = 1;

for문을 1부터 n까지 돌린다.

여기서 if, else if, else 구문이 들어가는데

 

1. if에는 taliTable[0] 보다 a[i]가 작을 때 taileTable[0] = a[i] 이다.

 

2. else if에는 tailTable[length-1]보다 a[i]가 클 때 tailTable[length]에 a[i]를 넣고 length += 1 해준다.

 

3. else에는 1, 2번에 해당되지 않을 경우엔 Arrays.binarySearch메소드로 tailTable에 들어갈 적절한 위치를 찾고

   교체해준다. binarySerach에 경우 배열에 찾으려는 값이 있을 경우엔 값이 있는 곳을 리턴하고

   없을 경우엔 삽입할 위치를 음수 형태로 리턴하는데

   여기서는 삽입이 아니라 교체이기 때문에 리턴 받은 값에서 -1을 곱하고 다시 1을 빼준다.

   리턴 받은 값이 -2 인경우엔 인덱스 1에 교체를 해준다.

 

이 과정을 통해 tailTable의 마지막 값보다 큰 경우엔 추가가 되면서 가장 긴 증가하는 부분 수열의 길이를 찾게 된다.

3번 과정을 통해 마지막 값은 항상 더 작은 값으로 계속해서 바뀐다.

 

예를 들어

10 50 10 20 30 40 인경우엔

 

10 50 -> i가 1일 때

10 50 -> i가 2일 때

10 20 -> i가 3일 때

10 20 30 -> i가 4일 때

10 20 30 40 -> i가 5일 때 

이런 식으로 tailTable이 채워져 가고 결국엔 길이 4를 리턴한다.

 

코드를 통해 O(nlogn)의 LIS알고리즘을 보자.

import java.util.Arrays;
import java.util.Scanner;
 
public class Q2352 {
    static int lis(int [] a) {
        int [] tailTable = new int[a.length];
        
        tailTable[0] = a[0]; // 초기값
        int length = 1;
        
        for(int i=1; i<a.length; i++) { //후보값이 처음값보다 작을 때
            if(tailTable[0] > a[i]) {
                tailTable[0] = a[i];
            }
            else if(tailTable[length-1] < a[i]) { //후보값이 마지막값보다 클 때
                tailTable[length] = a[i];
                length+=1;
            }
            else { //그 외의 경우엔 적절한 위치에 교체한다.
                int idx = Arrays.binarySearch(tailTable, 0, length, a[i]);
                idx = (idx < 0) ? -idx -1 : idx;
                tailTable[idx] = a[i];
            }
        }
        return length;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] a = new int[n];
        for(int i=0; i<n; i++) {
            a[i] = scan.nextInt();
        }
        System.out.println(lis(a));
    }
}