[99클럽 코테 스터디 31일차 TIL] 줄세우기 - 백준 2631

LIS 변형 문제이다.

 

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

문제 내용KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다.
선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다.
선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다.
이동 도중에 보니 아이들의 번호순서가 바뀌었다.
그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다.
그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.
3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자.
그러면 다음과 같은 순서가 된다. -> 3 7 4 5 2 6 1
이제, 7번 아이를 맨 뒤로 옮긴다. -> 3 4 5 2 6 1 7
다음 1번 아이를 맨 앞으로 옮긴다. -> 1 3 4 5 2 6 7
마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다. -> 1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다.
위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다.
따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 
번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

[입력]
첫째 줄에는 아이들의 수 N이 주어진다.
둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다.
N은 2 이상 200 이하의 정수이다.

[출력]
첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

풀이 접근

문제가 길다. 처음에는 링크드 리스트를 구현해서 각 요소를 직접 옮겨가며 풀어야하나 생각했다.

그런데 몇가지 테스트 케이스를 만들어보는 과정에서 LIS 변형 문제임을 알았다.

 

앞과 뒤에 숫자의 크기를 활용해야할것 같다는 느낌이 들었고, 예제 케이스를 포함에서 아래 3개의 케이스를 활용했다.

3 7 5 2 6 1 4
2 3 1
3 2 1

각각 정답은 4, 1, 2 이다.

 

케이스들에서 각 요소마다 뒤로 오는 큰 수의 개수를 세어보기도 했고, 앞에 있는 작은 수의 개수를 세어보기도 했다.

한참을 숫자 놀이를 하다가 이미 정렬된 수는 움직이지 않는다는 것을 깨달았다.

 

첫번째 케이스를 보자.

3 7 5 2 6 1 4
3   5   6

이미 정렬된 가장 긴 요소는 3 5 6이다. 그리고 이게 바로 LIS이다.

LIS의 길이를 구하면 나머지 요소들은 정렬해야할 수들이 된다.

따라서 전체 요소 - LIS길이(이미 정렬된 요소의 수)를 구하면 정답이다.

 

여기서 LIS의 정확한 요소가 아닌 길이만을 요구하기 때문에 이진탐색을 활용했다.

최종 코드 - Swift

let n = Int(readLine()!)!
let nums = (0..<n).map { _ in Int(readLine()!)! }
var lis: [Int] = []
for num in nums {
    if lis.isEmpty || lis.last! < num {
        lis.append(num)
    } else {
        var left = 0, right = lis.count - 1
        while left < right {
            let mid = (left + right) / 2
            if lis[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }
        lis[left] = num
    }
}
print(n - lis.count)

Conclusion

동적계획법이자 LIS 문제를 아는게 중요한 포인트였다.

생각보다 빨리 알아서 풀 수 있었다.