[백준] 3745번 - 오름세(Java)

풀이

키워드

• DP
• 이분 탐색
• LIS

 

LIS(최장 증가 부분 수열)

  이분탐색에서 주로 나오는 LIS문제였다. DP랑 같이 합해져서 나오는 문제 중 자주 나오는 유형인 것 같다. 이런 LIS의 경우 방식은 다음과 같다.

 

  1. List를 만들고 첫 번째 원소를 넣는다.

  2. 다음 원소(Next)부터는 list의 맨 마지막 원소(Last)와 비교하며 조건마다 특정한 작업을 수행한다.

     (조건 1) Last < Next

        list의 마지막 뒤에 Next를 집어넣는다.(add())

     (조건 2) Last >= Next

        list 원소 중 Next와 같거나 Next보다 작으면서 가장 비슷한 원소의 바로 다음 원소를 삭제하고 그 자리에 Next를 넣는다. (가령, Last = 3 이고 List = [1, 2, 4]였다면 4자리에 3이 들어가는 것이다.)

 

  이렇게 할 경우, (조건 1)에 의해 증가수열의 길이를 늘려가면서, (조건 2)에 의해 현재 증가수열보다 더 좋은 조건의 수열을 만날 경우, 그 수열로 수정해줄 수 있다. 이 때, 수정한다고 해도 [수정된 수열의 길이]가 [기존 수열의 길이]보다 길지 않다면, 결국 내가 현재 구하는 [최장증가수열의 길이]는 [수정된 수열의 길이]가 아닌 [기존 수열의 길이]가 된다는 것이 포인트이다.  

 

이분탐색

  이 때, Next가 들어갈 위치를 탐색하는 과정에서, 브루트포스로 일일이 탐색하면 시간이 너무 오래 걸린다. 여기서 이분탐색이 등장한다. List 안의 원소들을 이분탐색하여 Next가 들어갈 위치를 찾는 것이다.

 

  이분탐색은 매번 쓸 때마다 헷갈리는데, 이번에 제대로 정리하자.

     1. while 문 조건은 (start <= end)로 하자. 그래야 모든 원소를 탐색할 수 있다.

     2. mid에 따른 조건은 3가지로 분기하자.

        2-1. mid < Next

           end = mid-1

        2-2. mid == Next

           break;

        2-3. mid > Next

           start = mid+1

     3. 각 조건에 필요하다면 mid에 변화를 줄 수 있다.

           예시로, 이번 문제의 경우 Next가 자신보다 작으면서 가장 비슷한 숫자 바로 다음에 와야 하므로, 2-3조건에 추가적으로 mid++를 주었다. 이후 while문이 break되더라도 mid는 [작으면서 가장 비슷한 숫자]가 아닌 그 다음 위치에 추가될 수 있도록 하기 위함이다.

 

입력

  이번 문제의 경우, 입력에 여러 테스트케이스가 존재했는데, 총 테스트케이스가 주어지지 않았다. 이 경우 Scanner의 .hasNext()를 사용하면 되지만, Scanner 사용 시 속도가 너무 느려진다. 그래서 BufferedReader를 사용하는 방법을 알아보았다.

 

String input = null;

while ((input = br.readLine()) != null)

 

즉, 아무 입력이 없어도 .readLine()은 애러 없이 작동한다. 다만 null을 받아 올 뿐이다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String input = null;
        
        while((input = br.readLine()) != null) {
            int N = Integer.parseInt(input.trim());
            int [] arr = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());   
            }
            
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(arr[0]);
            for (int i = 1; i < N; i++) {
                int comp = list.get(list.size()-1);
                if (comp < arr[i]) {
                    list.add(arr[i]);   
                }
                else {
                    int start = 0;
                    int end = list.size()-1;
                    int mid = 0;
                    while(start <= end) {
                        mid = (start + end) / 2;
                        int cur = list.get(mid);
                        if (arr[i] < cur) {
                            end = mid - 1;   
                        }
                        else if (arr[i] == cur) {
                            break;   
                        }
                        else {
                            start = mid + 1;   
                            mid++;
                        }
                    }
                    list.set(mid, arr[i]);
                }
            }
            sb.append(list.size()).append("\n");
        }
        System.out.print(sb);
    }
}

---

출처 : https://www.acmicpc.net/problem/3745

3745번: 오름세