사용한 알고리즘
알고리즘 설명
- 각 전구는 1개의 스위치에 연결되어 있고 중복되는 경우가 없다.
- 위를 이용하여 각 전구가 몇번째 스위치에 연결되는지를 알아낸다.
- 앞쪽 전구부터 몇 번째 스위치에 연결되는지 알 수 있으며, 전선이 꼬이지 않기 위한 조건을 만족시키는 조건은 아래와 같다.
- (SW_i < SW_j && Light_i < Light_j) 또는 (SW_i > SW_j && Light_i > Light_j)임을 만족해야 교차하지 않는다.
- 먼저 앞쪽 전구부터 보게 되면 뒤쪽에 있는 전구와 교차하지 않을 조건은 자신의 SW보다 큰 값을 가질때 이다.
- 이는 전구의 적혀있는 스위치의 위치 값의 최장 수열을 찾는 것과 동치이다.
- 이는 LIS(Longest Increse Subsequence)를 찾는 것이며 이를 찾는 방법은 Segment Tree 형태와 BST(Binary Search Tree)를 사용하는 방법이 있는데 여기에서는 BST 사용하였다.
- lis 라는 배열을 생성하고 앞에서 부터 전구의 스위치 위치 값을 lis에 저장하는데, 이 배열은 증가하는 형태로 저장되어야 한다.
- lis에 저장할 때에 나중에 LIS를 만족하는 스위치 위치를 찾기 위해서 trace 배열에 저장하는 index 위치와 스위치 위치를 저장한다.
- lis 배열의 길이를 찾아내고, trace에서 뒤에서부터 누를 수 있는 스위치를 찾아 낸다.
- 스위치의 위치 값을 스위치의 번호 값으로 변경하고, 이를 sorting하여 출력한다.
풀이
// baekjoon 2550 yechan
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N=100001;
int N, top[MAX_N], bottom[MAX_N], idx[MAX_N];
int main() {
scanf("%d", &N);
// i번째 위치의 스위치 번호는 top(i)
// 스위치 번호 j의 위치는 idx(j)
for (int i=0; i<N; i++) {
scanf("%d", &top[i]);
idx[top[i]]=i;
}
// i번째 전구의 스위치 위치는 bottom(i)
for (int i=0; i<N; i++) {
int x;
scanf("%d", &x);
bottom[i]=idx[x];
}
// LIS 수열을 찾기
vector<int> lis(N+1, MAX_N);
vector<pair<int,int>> trace;
for (int i=0; i<N; i++) {
// lis 배열의 증가 수열 형태를 지키면서 적을 수 있는 lis의 위치 index
int index = lower_bound(lis.begin(),lis.end(), bottom[i]) - lis.begin();
// lis에 스위치 위치 저장
lis[index] = bottom[i];
// 나중에 tracking하기 위해 trace배열에 저장
trace.push_back({index, bottom[i]});
}
// lis 배열의 길이 cnt 찾기
int cnt=0;
for (int i=0; i<N; i++) {
if (lis[i] == MAX_N) break;
cnt++;
}
printf("%d\n", cnt);
// 배열은 0부터 시작하기 때문에 cnt 값을 1 빼줌
cnt--;
int tlen = trace.size();
vector<int> ansIdx;
for (int i=tlen; i>=0; i--) {
// trace 뒤에서부터 각 위치에 들어간 스위치 위치 번호 찾기
if (trace[i].first != cnt) continue;
ansIdx.push_back(trace[i].second);
cnt--;
}
// 스위치 위치를 스위치의 번호로 변경하여 ans에 저장
vector<int> ans;
for (int i=0; i<ansIdx.size(); i++)
ans.push_back(top[ansIdx[i]]);
// 결과 출력을 위해 정렬
sort(ans.begin(), ans.end());
// 결과 출력
for (int i=0; i<ans.size(); i++) {
printf("%d", ans[i]);
if (i != ans.size()) printf(" ");
else printf("\n");
}
return 0;
}
