[Algorithm]Baekjoon 2568번 : 전깃줄 - 2

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

2568번: 전깃줄 - 2

 

 
 
using namespace std;
 
struct Node
{
    int aNum;
    int bNum;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.aNum < b.aNum;
}
 
int n, a, b;
vector<Node> nodes;
int firstNum[500001] = { 0 };
bool check[500001] = { false };
vector<int> lis;
vector<int> indices;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        nodes.push_back({ a,b });
        firstNum[b] = a;
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
    lis.push_back(nodes[0].bNum);
    indices.push_back(0);
 
    for (int i = 1; i < nodes.size(); ++i) // 수열 순회
    {
        int searchedIndex = lower_bound(lis.begin(), lis.end(), nodes[i].bNum) - lis.begin();
        
        if (searchedIndex == lis.size()) // nodes[i]가 큼. 즉 오름차순형성 가능.
        {
            lis.push_back(nodes[i].bNum);
        }
        else // 오름차순 형성 불가능. 기존값 대체
        {
            lis[searchedIndex] = nodes[i].bNum;
        }
 
        indices.push_back(searchedIndex);
    }
 
    int indexToZero = lis.size()-1; // lis 크기.
    
    for (int i = indices.size() - 1; i >= 0; --i)
    {
        if (indices[i] == indexToZero)
        {
            int secondNum = nodes[i].bNum;
            check[firstNum[secondNum]] = true;
            --indexToZero;
        }
    }
 
    cout << n - lis.size() << endl;
 
    for (int i = 0; i < nodes.size(); ++i)
    {
        if (check[nodes[i].aNum] == false)
        {
            printf("%d\n", nodes[i].aNum);
        }
    }
}

LIS(가장 긴 증가하는 부분수열)을 구하는 문제인데, 단순히 크기뿐만 아니라 해당 부분수열의 원소들까지도 전부 구해야한다. 

기존에 사용했던 DP풀이는 N^2의 시간복잡도를 가지기 때문에 이 문제에서는 적용할 수 없다. (n이 최대 10만이라서)

그렇기 때문에 새로운 풀이를 적용한다. 새로운 풀이는 N logN으로 해결 가능하다.

 

일단 이 문제가 LIS문제인 이유는, A전봇대를 기준으로 오름차순정렬을 하면 이후 B전봇대의 숫자값들이 수열을 이룬다.

서로 교차되지 않으려면 B전봇대의 숫자값들이 오름차순을 유지해야하기 때문에, 결국 최대 오름차순크기와 그 원소들을 구하는 문제로 재해석되기 때문이다.

 

lis컨테이너(벡터든 배열이든)를 따로 선언 후, B전봇대의 숫자값들을 처음부터 접근해본다.

불필요한 if문을 없애기 위해 미리 첫번째전봇대의 숫자값을 넣어놓는다.

그럼 두번째 B전봇대숫자값부터 접근하며 다음과같이 로직을 수행한다.

 

1. 매 차례마다 lis에서, 현재차례의 B전봇대숫자값의 lower_bound값을 구한다.

2. lower_bound의 결과값, 즉 B전봇대숫자값보다 크거나 같은숫자의 인덱스를 구했을텐데 그러면 아래와 같이 수행한다.

   2-1 => 구한 인덱스값이 lis.size()와 동일하다면, 즉 lis의 어떠한 원소보다 B전봇대숫자값이 크다면, 그대로 v에 넣어준다. 이렇게 함으로써 오름차순을 유지하게 된다.

   2-2 => 구한 인덱스값이 lis.size()보다 작다면, 해당 인덱스의 값과 바꿔치기한다. 그럼으로써 오름차순을 유지하게 된다.

 

최대 n번을 순회하며, logN의 시간복잡도를 지닌 lower_bound를 수행하기 때문에 N.logN의 시간복잡도로 LIS의 크기를 구할 수 있게 된다..! 

물론 딱 크기'만'.

 

여기서 lis컨테이너에 들어있는 원소들은 실제 lis를 이루는 올바른 원소들이 아니다. 그저 lis의 최대크기를 구하기위해 최대한 원소들 사이의 갭을 줄이기위해 업데이트하는 과정일 뿐이다. 

이전 문제에서도 말했었지만, 갭을 줄이면 lis크기가 커질 가능성이 '반드시' 증가하기 때문이다.

그렇기때문에 그냥 업데이트순서에따라 원소들이 이리저리 바뀌며, 정답이아닌 원소가 나중에 로직을 수행한다면 해당 원소가 lis컨테이너에 들어있게 되기 때문에, 크기만 맞고 내부원소들은 정답이 아니라는 것이다.

 

그렇기 때문에 indices라는 따로 인덱스를 저장하는 컨테이너를 만든다.

A를 기준으로 정렬된 B전봇대숫자값을 순회하면서(nodes) 해당 숫자들이 lis의 몇번째 인덱스에 업데이트 됐는지 따로 저장한다.

그걸통해 실제로 lis를 구성하는 B의값이 어떤것인지 알 수 있고, 처음에 미리 B의값으로 A값을 찾게 check라는 배열을 따로 해놨기 때문에, B의값을통해 연결된 A전봇대가 어떤것인지 체크해놓는다.

이후, 체크한것을 제외한 나머지 A전봇대를 출력해주면 된다.