[백준 2352] 반도체 설계

문제풀이

c++로만 풀다가 첨으로 java로 푼 문제이다.

가장 긴 오름차순 수열을 찾는 LIS문제와 동일하다.

 

마지막 인덱스 접근을 위해 초기에 0을 넣어두고 사용한다.

마지막 인덱스를 size-1로 접근하는데 없으면 에러뜨기때문..

 

마지막보다 큰값이 들어오면 뒤에 삽입. 작거나 같은값이 들어오면 lower_bound값을 찾아 그값과 변경한다.

 

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Baekjoon2352 {
 
    static int numPort;
    static List<Integer> port;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        numPort = scan.nextInt();
        port = new ArrayList<Integer>();
        port.add(0);
        for(int i=0;i<numPort;i++){
            int temp = scan.nextInt();
            if(port.get(port.size()-1) < temp) //끝값 보다 클
                port.add(temp);
            else {
                int idx = 0;
                for (int j = 0; j < numPort; j++) {
                    if (temp <= port.get(j)) {
                        idx = j;
                        break;
                    }
 
                }
                port.set(idx, temp);
            }
        }
        System.out.println(port.size()-1);
    }
}
 

 

문제 링크 : www.acmicpc.net/problem/2352

2352번: 반도체 설계