[백준] 11722번. 가장 긴 감소하는 부분 수열(JAVA)

문제

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

---

풀이(15분)

import java.awt.Point;
import java.util.*;
import java.io.*;

public class Main{

    static ArrayList<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        list.add(Integer.parseInt(st.nextToken()));
        for(int i = 1; i < n; i++){
            check(Integer.parseInt(st.nextToken()));
        }
        System.out.println(list.size());
    }

    public static void check(int x){
        int min = list.get(list.size() - 1);
        if(min > x){
            list.add(x);
            return;
        }
        int idx = findIdx(x);
        list.set(idx, x);
    }

    public static int findIdx(int x){
        int start = 0;
        int end = list.size() - 1;
        int mid = (start + end) / 2;
        while(start <= end){
            mid = (start + end) / 2;
            if(list.get(mid) == x){
                return mid;
            }
            if(list.get(mid) > x){
                start++;
                continue;
            }
            end--;
        }
        return mid;
    }

}

 

이 전의 11053과 같은 문제를 풀었다면 동일한 아이디어라는 것을 알 수 있다.

 

문제에서 제시된 입력 순서인 10 30 10 20 20 10을 순서대로 생각해보자.

1. 10을 넣는다. (리스트 상태 : 10)

2.10 30 은 불가능하므로 10을 30으로 바꾼다. (리스트 상태 : 30)

3. 30 10 은 가능하므로 10을 넣는다. (리스트 상태 : 30 10)

4. 30 10 20 은 불가능하므로 30 20으로 만든다. (리스트 상태 : 30 20)

5. 20은 넣을 수 없으니 넘어간다.

6. 30 20 10 은 가능하므로 넣는다.(리스트 상태 : 30 20 10)

 

이 문제를 풀어본 적이 없다면 아이디어가 이해하기 힘들 수 있으니 다음과 같이 생각해보자.

그 전에 규칙을 먼저 정리하자.

1. 리스트의 제일 끝보다 작은 숫자가 들어온다면 리스트의 끝에 넣는다.

2. 리스트의 끝보다 큰 숫자가 들어온다면 리스트 안에 숫자 중에 자기보다 작은 숫자 중 제일 차이가 나지 않는 숫자를 대체한다.

 

자. 문제로 돌가서 생각해보자.

1. 10이 왔다. 넣는다! -> 생각 할 이유가 없다.

2. 30이 왔다! 규칙(2)대로 10을 30으로 변경한다. -> 의문이 생길 수 있다.

3. 10이 왔다. 규칙(1)대로 30 10으로 만든다. 자. 여기서 2번의 의문을 해결해보자. 왜 대체를 하는 것일까?

어차피 10을 30으로 바꾼다는 것은 이후에 10~30 사이인 숫자가 오면 30을 시작점으로 하면 길이가 2가 될 것이다.

반대로 10이 었다면 길이가 1일 것이다.

또한, 1~10 사이의 숫자가 오더라도 30과 10 모두 길이가 2가 된다.

즉, 대체하여 진행시키는 것이 옳은 방법이라는 것이다.

이후 과정은 동일하게 규칙을 반복한다.