백준 7570 줄 세우기

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

주어진 수열을 번호 순서로 정렬하되, 각 숫자들은 맨 앞이나 맨 뒤로밖에 움직일 수 없다.

번호순서대로 만드는 최소 움직임 수를 출력하는 문제이다.

번호의 수가 최대 1,000,000이라서 어떻게 풀어야 할 지 정말 막막해 구글링을 통해 아이디어를 얻은 후 시도하였다.

아이디어는 '가장 긴 연속되는 부분 수열을 찾는다' 였다.

왜 그런지에 대해서 예시를 통해 시뮬레이션 해보면 알 수 있었다.

9 6 2 7 3 4 1 5 8

이런 예시가 있다고 해 보자.

가장 긴 부분 수열은 위 예시에서는 (2, 3, 4, 5)이다.

그럼 적어도 2, 3, 4, 5의 숫자는 맨 뒤나 앞으로 보낼 필요가 없다.

따라서 4개의 숫자를 고정시키고, 나머지 숫자들을 순서에 맞춰 하나씩 맨 앞이나 맨 뒤로 보낸다.

1. 9 6 2 7 3 4 1 5 8
2. 1 9 6 2 7 3 4 5 8 (1을 앞으로)
3. 1 9 2 7 3 4 5 8 6 (6을 뒤로)
4. 1 9 2 3 4 5 8 6 7 (7을 뒤로)
5. 1 9 2 3 4 5 6 7 8 (8을 뒤로)
6. 1 2 3 4 5 6 7 8 9 (9를 뒤로)

이런 식으로 연속되는 숫자를 제외한 나머지 숫자들은 연속 수열의 앞쪽으로 보낼 숫자라면 큰 숫자부터, 뒤로 보낼 숫자라면 작은 숫자부터 보내 정렬한다.

이렇게 가장 긴 연속되는 부분 수열의 길이를 구해 전체에서 빼면 최소 횟수를 얻을 수 있다는 것을 알았다.

그럼 이제 가장 긴 연속되는 부분 수열을 구해보자.

앞서 말했다시피 N은 최대 1,000,000이므로 부분 수열을 구할 때 $O(nlogn)$ 이내로 구해야 한다.

따라서 나는 map 자료구조를 이용해 $O(n)$으로 풀이하였다.

방법은 다음과 같다.

1. 배열을 순회하며, 각 (원소 - 1)의 값이 map에 존재하는지 검사한다.
2. 원소 - 1 값이 map에 없다면 (원소, 1)을 key-value로 추가한다.
3. 원소 - 1 값이 map에 있다면 (원소, 해당 값 + 1)을 key-value로 추가한다.
4. 위 과정 동안에 map[n - 1] + 1의 값이 max보다 크다면 갱신한다.

위와 같은 예시인 9 6 2 7 3 4 1 5 8 가 있다고 하자.

1. 원소 9에 대해, map[8]은 없으므로 map[9] = 1을 넣는다. (최댓값 1)
2. 원소 6에 대해, map[5]는 없으므로 map[6] = 1을 넣는다.
3. 원소 2에 대해, map[1]은 없으므로 map[2] = 1을 넣는다.
4. 원소 7에 대해, map[6]은 1이므로 map[7] = 1 + 1을 넣는다. (최댓값 2)
5. 원소 3에 대해, map[2]는 1이므로 map[3] = 1 + 1을 넣는다.
6. 원소 4에 대해, map[3]은 2이므로 map[4] = 2 + 1을 넣는다. (최댓값 3)
7. 원소 1에 대해, map[0]은 없으므로 map[1] = 1을 넣는다.
8. 원소 5에 대해, map[4]는 3이므로 map[5] = 3 + 1을 넣는다. (최댓값 4)
9. 원소 8에 대해, map[7]은 2이므로 map[8] = 2 + 1을 넣는다.

따라서 (2, 3, 4, 5)가 최댓값 4로 가장 긴 연속 부분 수열임을 알 수 있다.

따라서 전체 길이 9에서 부분 수열 길이인 4를 뺀 5를 출력한다.

import java.util.*

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val children = readLine().split(' ').map{it.toInt()}

    val tm = TreeMap<Int, Int>()

    var max = 1
    for(num in children){
        if(tm[num - 1] == null){
            tm[num] = 1
        }else{
            tm[num] = tm[num - 1]!! + 1
            if(max < tm[num]!!)
                max = tm[num]!!
        }
    }
    print(N - max)
}