이번 문제는 백준의 플래티넘 5 전깃줄 2 문제이다.
이전에 전깃줄 1 문제를 푼 적이 있었는데, 해당 문제의 심화 버전이다.
문제를 차근차근 읽어보도록 하자.
번호가 순서대로 적힌 기둥이 있고, 해당 기둥에 전깃줄을 연결한다.
단 해당 전깃줄들이 하나도 겹치지 않게 하고 싶다.
최소 몇 개의 전깃줄을 제거해야 모든 전깃줄이 겹치지 않을 수 있을까?
이 때 전깃줄은 최대 100,000개가 주어질 수 있으며,
각 기둥의 번호는 500,000 까지 가질 수 있다.
LIS
이전의 전깃줄 1 문제는 전형적인 LIS 문제였다.
원리는 아래와 같다.
모든 연결된 전깃줄을, 왼쪽 기둥 기준으로 오름차순 정렬한다.
기둥의 번호는 순서대로 적혀있기 때문에, 정렬해도 지장이 없다.
이제 오른쪽 기둥을 유심히 봐야한다.
오른쪽 기둥은 분명 순서대로 정렬이 되어 있지 않을 것이다.
하지만 잘 생각해보면, 오른쪽 기둥은 오름차순으로 정렬되어야 한다.
왜? 그래야 전깃줄이 겹치지 않을 것이다.
위의 그림과 같이 전깃줄이 연결되어 있다고 생각해보자.
왼쪽은 이미 오름차순으로 정렬이 잘 되어있다.
이 때, 오른쪽 기둥을 잘 살펴보면 겹치지 않는 전깃줄의 특징을 알 수 있다.
2 4 5 6 7 과 같이 오름차순으로 정렬이 되어야 한다는 점이다.
따라서 이 문제를 푸는 핵심은 가장 긴 증가하는 부분 수열과 같다.
시간 복잡도
하지만 이번 문제는 전깃줄 2로, 기존의 방식으로는 풀 수 없다.
왜냐하면 주어지는 전깃줄의 수가 늘어났기 때문이다.
또한 잘라야 하는 전깃줄을 차례로 출력해주어야 한다.
기본적으로 동적계획법을 활용한 LIS의 시간복잡도는 O(N^2)이다.
그럼 100,000개의 전깃줄이 주어지는 경우엔 반드시 시간초과가 발생한다.
즉, 우리는 시간복잡도를 O(N^2) 아래로 내려서 LIS를 풀어야 한다.
이분 탐색
LIS의 원리를 잘 생각해보자.
하나의 수를 잡고 해당 수보다 앞에 있는 수 중 작은 수를 찾는 것이다.
작은 수를 만났을 때, max(dp[i], dp[j] + 1)을 통해 최대 길이를 갱신한다.
이와 유사하게, 우리는 이분 탐색을 사용해서 LIS의 길이를 알 수 있다.
핵심은 현재 가리키는 수보다 큰 수가 처음 나오는 위치를 구하는 것이다.
예를 들어, 문제의 예시에 나온 8 2 9 1 4 6 7 10 이라는 배열을 예로 들어보자.
가장 먼저 위와 같이 8이 배열의 가장 앞에 들어간다.
다음으로 2를 가리키게 되는데, 이 때 이분탐색이 필요하다.
LIS의 길이를 갱신하기 위해 2보다 크거나 같은 수가 처음으로 등장하는 위치,
즉 배열 내에서 2의 lower bound를 계산하는 것이다.
그럼 배열의 가장 앞인 0번째 칸 8이 추출되게 되고,
아래와 같이 해당 칸을 현재 가리키고 있던 2로 변경한다.
다음으로 가리키는 수는 9로, 2보단 크므로 그냥 삽입하면 된다.
그 다음으로 가리키는 수는 1로, 9보다 작기 때문에 이분탐색을 한다.
구해지는 lower bound는 가장 앞에있는 2가 된다.
배열의 모양은 아래와 같아지게 될 것이다.
다음으로 가리키는 수는 4로, 마지막 수인 9보다 작다.
이번에도 lower bound를 계산하게 되며, 9와 4를 교체한다.
다음으로는 6 7 10을 차례로 가리키게 되는데,
이 수들은 모두 배열의 마지막 수보다 크게 된다.
따라서 배열은 최종적으로 아래와 같이 만들어지게 된다.
즉, 우리가 구하는 최장 증가 부분 수열의 길이는 5가 된다.
전깃줄의 총 길이에서 해당 수를 빼면, 지워야 하는 전깃줄 수인 ```3``이 나온다.
왜 이런 계산이 가능한 것일까?
수열을 진행하며, 항상 작은 값을 우선으로 채택을 했으며,
끊기는 지점, 즉 수가 작아질 때는 큰 수 중 가장 작은 수를 버렸다.
이렇게 되면 자연스럽게 오름차순으로 배열이 정렬이 되는 것이다.
지워야 하는 전깃줄의 번호
이제 관건은 지워야 하는 전깃줄의 번호를 출력해야 하는 것이다.
이를 위해서 우리는 LIS를 갱신할 때, 인덱스를 따로 저장해야 한다.
LIS가 정상적으로 갱신될 때는, LIS의 크기를 저장한다.
더 작은 수가 나와 수의 교체가 필요할 때는, 교체된 위치를 저장한다.
이렇게 되면 이후 인덱스 배열을 조사할 때, 자를 전깃줄을 확인할 수 있다.
예를 들어, 위의 예시였던 8 2 9 1 4 6 7 10를 다시 보자.
LIS 배열이 채워질 때 인덱스 배열은 어떻게 채워질까?
위에서 풀었던 대로라면, 0 0 1 0 1 2 3 4가 될 것이다.
이제 인덱스 배열을 뒤에서 부터 한 번 훑어보자.
LIS의 마지막 포인터를 기준으로 비교를 진행한다.
인덱스 배열의 값과 LIS의 포인터의 위치가 같다면, 포인터를 줄인다.
하지만 인덱스와 포인터 위치가 다르다면? 잘라야 할 선이라는 것이다!
왜? 인덱스와 포인터 위치가 같을 땐, LIS를 구성한 위치라는 의미이다.
하지만 위치가 다르다는 것은 수의 교체가 발생했다는 의미가 되고,
해당 위치의 전깃줄은 LIS를 구성할 수 없다는 말이 된다!
따라서 뒤에서 부터 훑으며 저장된 전깃줄의 번호가 잘라야 할 선이 된다.
최종적으로 아래와 같이 구현되었다.
sort(wire_vec.begin(), wire_vec.end());
// 연결되는 앞부분 기준으로 정렬했을 때
// 전선의 뒷 쪽이 모두 오름차순이면 연결 가능함.
LIS.push_back(wire_vec[0].second);
idx.push_back(0);
for (int i = 1; i < num; i++) {
int curr_pillar = wire_vec[i].second;
if (LIS.back() < curr_pillar) {
// LIS의 가장 뒤보다 현재 번호가 크면
idx.push_back(LIS.size());
// 기둥 번호를 index 배열에 저장한다.
LIS.push_back(curr_pillar);
// 바로 LIS에 그냥 저장한다.
}
else {
// 만약 LIS의 가장 뒤보다 현재 번호가 작거나 같으면
vector<int>::iterator iter = lower_bound(LIS.begin(), LIS.end(), curr_pillar);
*iter = curr_pillar;
// lower_bound를 통해 최초로 발견되는 현재 번호 이상의 번호 위치를 찾는다.
idx.push_back(iter - LIS.begin());
cout << iter - LIS.begin() << '\n';
// 해당 위치를 index 배열에 저장한다.
}
}
cout << num - LIS.size() << '\n';
int curr_ptr = LIS.size() - 1;
for (int i = idx.size() - 1; i >= 0; i--) {
if (curr_ptr == idx[i])
curr_ptr--;
else
answer.push_back(wire_vec[i].first);
}
for (int i = answer.size() - 1; i >= 0; i--)
cout << answer[i] << '\n';높은 난이도 만큼 상당히 어려운 문제였다.
이런 문제를 코딩테스트에서 맞닥뜨렸다면, 절대 풀 수 없었을 것이다.
지금 잘 익혀놓고, 다음에 한 번 더 풀어봐야 할 것 같다.