[Algorithm] 백준 DP 문제 - 줄세우기(2631) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 줄세우기 자바 풀이를 작성하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2631

2631번: 줄세우기

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        int[] map = new int[n];
        for (int row = 0; row < n; row++) map[row] = parseInt(br.readLine());
        int lis = getLISByBinarySearch(map); // 이진 탐색으로 LIS 길이 찾기
        
        System.out.println(n - lis); // 총 길이에서 LIS 개수를 빼면 이동가능한 길이가 나옴
    }
    
    static int getLISByBinarySearch(int[] arr) { // 이진 탐색
        List<Integer> dp = new ArrayList<>(); // dp 저장
        
        for (int num : arr) {
            if (dp.isEmpty() || num > dp.get(dp.size() - 1)) dp.add(num); // 처음이거나 마지막 숫자보다 크면 업데이트
            else {
                int left = 0, right = dp.size() - 1;
                while (left < right) { // 이진 탐색
                    int mid = left + (right - left) / 2;
                    if (dp.get(mid) < num) left = mid + 1;
                    else right = mid;
                }
                dp.set(right, num); // 위치에 값 업데이트 
            }
        }
        
        return dp.size();
    }
}

 

2. 풀이 중점 사항

 

이 문제는 정렬되지 않은 숫자가 있을 때, 각 위치를 이동하여 최소 숫자로 정렬하는 문제입니다.

 

순열 1, 5, 2, 9 가 주어져 있다고 예를 들겠습니다.

이 경우 2를 5 앞에 놓게 되면 1 2 5 9로 정렬을 할 수 있습니다.

 

1, 5, 2, 3, 7, 6이 주어졌다고 가정하겠습니다.

3의 뒤에 5을 이동시키고, 7을 6 뒤에 이동시키면 2번 안에 이동을 마칠 수 있습니다.

 

이는 최장 증가 부분 수열을 찾은 후, 최장 증가 부분 수열 내부로 각각 원소들을 이동시키면 되는 것입니다.

1      2        3         6          이 최장 증가 부분 수열이므로 

                      5          7     을 위치시키면 문제를 해결할 수 있습니다.

 

즉 정답은 총 개수 - 최장증가 부분 수열 개수를 빼면 해결 할 수 있습니다.

 

 

3. LIS 이진탐색으로 해결하기

 

이진 탐색은 O(logN)으로 LIS를 구할 수 있습니다. 이러한 기능이 가능한 이유는 만약 주어진 숫자가 마지막 인덱스보다 크다면 바로 추가하고, 만약 아니라면 최대로 큰 값을 찾아서 계속 업데이트하되, 그 찾는 과정을 이진 탐색으로 수행하기 때문입니다.

이 과정에서 중요한 점이, 이진 탐색으로 수행할 때, 그 값을 add 하는 것이 아니라 set으로 업데이트하는 것입니다.

즉 최장 증가 부분 수열이 5개라면 6개로 만드는 것이 아니라 중간에 값만 바꾸는 것이기 때문에 최장 증가 부분수열의 크기는 변하지 않고, 탐색한 위치의 값만 수정되게 되는 것입니다. 

 

static int getLISByBinarySearch(int[] arr) { // 이진 탐색
    List<Integer> dp = new ArrayList<>(); // dp 저장

    for (int num : arr) {
        if (dp.isEmpty() || num > dp.get(dp.size() - 1)) dp.add(num); // 처음이거나 마지막 숫자보다 크면 업데이트
        else {
            int left = 0, right = dp.size() - 1;
            while (left < right) { // 이진 탐색
                int mid = left + (right - left) / 2;
                if (dp.get(mid) < num) left = mid + 1;
                else right = mid;
            }
            dp.set(right, num); // 위치에 값 업데이트
        }
    }

    return dp.size();
}

 

먼저 DP를 리스트로 설정합니다. 

• 2, 5, 3, 7 숫자가 주어졌다면 하나씩 배열에 담긴 숫자를 탐색합니다.
• 2는 dp가 비어있으므로 dp에 추가합니다.
• 5는 dp의 마지막 값인 2보다 크므로 dp에 추가합니다.
• 3은 5의 마지막 값보다 작으므로 이진 탐색을 수행합니다.
• left = 0, right = 1이고 mid = 0 + 1 / 2 = 0 이므로, left = mid + 1입니다.
• left < right의 조건을 위배하므로 right를 업데이트하는데 right가 1이므로 5의 값을 대체합니다.
• 7은 dp의 마지막 값인 3보다 크므로 7을 추가로 넣습니다.
• 즉, 이진 탐색을 수행하며, 최장 부분 수열을 만족하며 값을 바꿔 끼는 것을 확인할 수 있습니다.

이를 통해 최장 증가 부분 수열의 크기를 구할 수 있습니다.

 

 

4. 최장 증가 부분 수열 전체를 이진 탐색으로 구하기

 

최장 증가 부분 수열을 위의 코드로 구하고 출력하게 된다면, 개수는 동일하지만 올바른 값이 출력되지 않습니다.

왜냐하면 이진 탐색으로 중간에 값을 set 하기 때문에 마지막 값이 변경되지 않는다면 중간의 값을 바꾸는 것이기 때문입니다.

따라서, 온전한 최장 증가 부분 수열을 구하려면 하단의 코드를 작성해야 합니다.

 

static List<Integer> lisOfBinarySearchList(int[] nums) {
    List<Integer> dp = new ArrayList<>();

    int[] idxs = new int[nums.length]; // 인덱스 저장할 배열
    int[] preIdxs = new int[nums.length]; // 이전 인덱스를 저장할 tmp 배열

    for (int i = 0; i < nums.length; i++) {
        if (dp.isEmpty() || nums[i] > dp.get(dp.size() - 1)) { // 리스트가 비어있거나 현재 리스트의 마지막 값보다 더 큰 경우
            if (!dp.isEmpty()) preIdxs[i] = idxs[dp.size() - 1]; // dp의 마지막 값을 임시 배열에 저장
            dp.add(nums[i]); // 값 추가하기
            idxs[dp.size() - 1] = i; // 인덱스를 저장할 색인 배열에 인덱스 업데이트
        } else { // 이진 검색 시작
            int left = 0, right = dp.size() - 1; // 초기화 양 끝
            while (left < right) {
                int mid = left + (right - left) / 2; // 중앙을 설정할 mid
                if (dp.get(mid) < nums[i]) { // 중간에 위치한 값보다 큰 경우 오른쪽 이진 검색
                    left = mid + 1; // left를 증가시켜서 위치를 옮김
                } else {
                    right = mid; // right를 미드로 설정하여 왼쪽 이진 탐색
                }
            }
            dp.set(right, nums[i]); // 중앙에 값을 대체함
            idxs[right] = i; // 대체한 인덱스 설정
            if (right > 0) preIdxs[i] = idxs[right - 1];
        }
    }

    List<Integer> lis = new ArrayList<>();
    int idx = idxs[dp.size() - 1];
    while (lis.size() < dp.size()) {
        lis.add(nums[idx]);
        idx = preIdxs[idx];
    }
    Collections.reverse(lis);
    return lis;
}

 

아래의 예시와 함께 설명하면 다음과 같습니다.

수열 2, 5, 3, 7이 주어져 있습니다.

arr은 배열 2, 5, 3, 7

dp는 이진 탐색으로 업데이트한 최장 증가수열을 저장할 dp

preIdxs는 Idx의 이전 인덱스 저장

Idxs는 최장 증가 부분 수열의 실제 값을 저장하기 위한 인덱스 

먼저 인덱스 0을 순회하면, dp가 비어있으므로 2를 저장합니다.

preIdxs[0] = idxs[0]      (0)

idxs[0] = 0

 

 

인덱스 1인 경우 arr[1] = 5가 2보다 크므로 5를 저장합니다.

preIdxs[1] = 0

idxs[1] = 1     

 

이것이 의미하는 바는, 가장 큰 최장 증가 부분 수열의 길이는 2입니다.

idx[dp.size() - 1]이 의미하는 바는 이 가장 긴 수열의 실제 값 (arr의 위치)를 저장한 인덱스입니다.

즉 arr[1]을 찾을 수 있습니다.

 

preIdx의 인덱스 1에 저장된 0은 다음 최장 증가 부분 수열에서 큰 값의 인덱스를 가리키고 있습니다.

 

 

 

인덱스가 2로 이동한다면, 

dp의 값은 업데이트가 되는데 5보다 3이 작지만 이진 탐색으로 right가 마지막 인덱스를 가리켜서 업데이트 됩니다.

이렇게 값이 더 커서 업데이트가 되는 경우가 아니라 이진 탐색으로 바뀌게 되는 경우는 idx를 먼저 업데이트합니다.

(개수가 증가하는 것이 아니라 내부의 값을 변경하므로)

따라서 idx가 가리키는 인덱스는 2로 수정됩니다.  preIdxs[2] = 0을 가리킵니다.

 

 

마지막 인덱스 3에 도달하면 7을 DP에 넣습니다.

preIdxs[3] = 2 (dp 사이즈 - 1)

idxs[2] = 3 (인덱스는 실제 arr의 위치를 가리킴)

 

총 나온 결과로 시뮬레이션을 확인하면 다음과 같습니다.

 

List<Integer> lis = new ArrayList<>();
    int idx = idxs[dp.size() - 1];
    while (lis.size() < dp.size()) {
        lis.add(nums[idx]);
        idx = preIdxs[idx];
}

• 최종 최장 증가 부분 수열을 찾기 위한 list를 선언합니다.
• dp.size() - 1의 값인 2를 인덱스로 하여 idxs 배열에서 찾습니다
• 값 3을 가지고 arr[3]의 값을 list에 추가합니다.
• 값 3으로 preIdxs[3] -> 다음 idx에서 찾을 인덱스 2를 가져와 idx로 업데이트 합니다.
• 인덱스 2로 arr[2]인 3을 찾습니다.
• 인덱스 2 preIdxs[2] = 0 을 다음 인덱스로 하여 값을 찾습니다.
• arr[0] = 2 

LIS 를 이진탐색으로 구현할 때, 임시 배열이 여러 개 생성되므로 많이 헷갈렸습니다.

실제 PPT로 그려가며 그 상황을 시뮬레이션하니, 이해할 수 있었습니다.

 

이상으로 줄세우기 자바 풀이를 마치도록 하겠습니다. 감사합니다.