[백준] 1965번. 상자 넣기(JAVA)

문제

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

---

풀이(20분)

import java.io.*;
import java.util.*;

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());
        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        list.add(arr[0]);
        for(int i = 1; i < n; i++){
            if(list.get(list.size() - 1) == arr[i]){
                continue;
            }

            if(list.get(list.size() - 1) > arr[i]){
                int idx = binarySearch(arr[i]); // 대체할 자리 찾기
                list.set(idx, arr[i]); // 값 대체
                continue;
            }

            list.add(arr[i]); // 가장 큰 값 들어올 경우 리스트 끝에 추가
        }

        System.out.println(list.size());

    }

    public static int binarySearch(int target){
        int start = 0;
        int end = list.size() - 1;
        int mid;

        while(start <= end){
            mid = (start + end) / 2;
            if(list.get(mid) == target){ // 찾으면 바로 반환
                return mid;
            }

            if(list.get(mid) < target){ // 목표치보다 작을 경우 start 를 변경
                start = mid + 1;
                continue;
            }

            end = mid - 1; // 목표치보다 클 경우 end 를 변경
        }

        return start;
    }
}

// 1 6 이 있었고 타겟이 2로 들어옴. 그럼 내가 원하는건 1 2 로 바뀌어야함.
// 그럼 start = 0, end = 1, mid = 0으로 시작함.
// 안 되니까 start = 1로 되고 while문 한번 더.
// 그럼 mid = 1 이 되고 값이 6이 뜨니까 end = 0이 됨.
// 여기서 끝나고 start = 1 이 반환됨.
// 즉 원하는 인덱스 변경 완료

// 왼쪽보다 크면 빼고 넣는다.
// 1
// 1 6
// 1 2
// 1 2 5
// 1 2 5 7
// 1 2 3 7
// 1 2 3 7
// 1 2 3 5
// 1 2 3 5 6
// 즉, 작으면 자기보다 크거나 같은 것 중 최소를 자기 자신으로 대체해야함.

 

가장 긴 증가하는 부분 순열을 찾는 LIS문제와 동일한 방법으로 해결했다.

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

 

1 6 2 5 7 3 5 6

 

라는 예제를 생각해 보자.

 

1을 먼저 넣는다.

 

1은 6에 들어갈 수 있으므로 1 6이 된다.

 

6이 최대 사이즈고 2에 들어갈 수 없으므로, 1을 2에 넣었다고 생각하자. 즉 1, 2가 된다.(박스를 가장 많이 겹치려면 최대인 박스가 가장 작을수록 유리하다.)

 

2는 5에 들어갈 수 있으므로 1 2 5가 된다.

 

5는 7에 들어갈 수 있으므로 1 2 5 7이 된다.

 

7은 3에 들어갈 수 없으므로 1 2 3 7이 된다.

-> 여기서 이해가 힘들 수 있다. 어떻게 1 2 3 7이 되는 것일까???

-> 현재 1 2 5 7까지의 정답은 4이다. 이걸 부정할 생각은 없다.

 

-> 기억을 초기화하고 1 6 2 5 7 3 5까지 있는 상황을 생각해 보자.

-> 그럼 어떻게 넣는 게 가장 많이 포갤 수 있는 것일까? -> 1 2 3 5도 된다는 것이다. 즉, 우리가 3까지만 생각했을 때 가졌던 1 2 3 7보다 1 2 3 5가 되는 것이 뒤에 6이 나올 때 값을 하나 늘릴 수 있는 효율적인 방법이 된다는 소리이다.

 

-> 그건 알겠는데 그럼 1 6 2 5 7 3 6이 나온다면??

-> 결과는 동일하다. 내가 하겠다는 것은 만약 최댓값보다 작은 값이 나온다면, 이 전의 리스트 중에 자기보다 크거나 같은 것 중에 최소인 것을 자기 자신으로 대체하겠다는 것이다.

-> 즉 1 2 5 7 -> 1 2 3 7 -> 1 2 3 6이 된다는 것. 다시 말하지만, 이렇게 해야 뒤에 7이 나오더라도 다시 1 2 3 6 7로 해서 값을 최대로 만들어줄 수 있기 때문이다.

 

만약 이해가 잘 되지 않는다면 11053번 문제를 꼭 다시 풀어보자!!