[백준]빌보의 생일(4442)

문제 링크 : [백준]빌보의 생일(4442)

4442번: 빌보의 생일

 

문제 설명

프로도와 샘이 각각 생일 파티에 참가한 사람들을 순서대로 앉힐 좌석표를 작성하였습니다.

두 좌석표가 일치하지 않을 수 있어서 새로운 좌석표를 만드는데, 원래 있던 두 좌석표와 다른 쌍이 최소가 되게 하려고 합니다.

이 때, 최소 다른 쌍의 수를 구하세요.

입력

N(참석자의 수, 1 <= N <= 100,000)

P(프로도가 작성한 좌석표)

S(샘이 작성한 좌석표)

3
Frodo Sam Bilbo
Sam Frodo Bilbo
5
A B C D E
B A D E C
0

 

출력

1
3

 

카테고리

#세그먼트트리 #펜윅트리

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. 새로운 좌석표를 구하는 것이 어려워 보입니다.
2. 하지만 주어진 좌석표 중 아무거나 하나를 기준으로 하면 됩니다.
3. 주어진 두 좌석표 모두와 다른 쌍이 있다면, 항상 하나를 기준으로 했을 때보다 다른 쌍의 갯수가 작거나 크게 됩니다.
4. 그렇다면 하나를 기준으로 다른 좌석표와 다른 쌍을 구하면 되는 문제로 바뀝니다.
5. I번째 사람을 예로들면 윗줄에서 I번째 사람보다 왼쪽에 있던 사람이, 아랫쪽에서 오른쪽에 있는 사람의 수를 세면 됩니다.
6. 5.를 구하기 위하여 윗줄의 1번부터 차례로 아랫쪽의 1번의 위치보다 오른쪽 사람의 수를 구하고, 1번의 아랫쪽 위치에 1을 더해줍니다.
7. 2번의 아랫쪽 위치보다 오른쪽에 있는 사람의 수를 구하고, 2번의 아랫쪽 위치에 1을 더해줍니다.
8. 6,7번을 반복하는데, 업데이트와 구간합이 계속 반복 되므로, 세그먼트 트리나 펜윅트리를 이용하면 됩니다.
9. 코드 구현은 펜윅트리 구간합을 쉽게 구하기 위하여 N부터 1번방향으로 구하였습니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#include<unordered_map>
#include<string.h>
using namespace std;
int n,i,p,t[100001];
long long a;
string s;
unordered_map<string,int>m;
void u(int p){
    while(p<=n)t[p]++,p+=p&-p;
}
int q(int p){
    int s=0;
    while(p)s+=t[p],p-=p&-p;
    return s;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    while(1){
        cin>>n;
        if(!n)break;
        m.clear();
        memset(t,0,sizeof(t));
        for(a=i=0,p=n;i<n;i++)cin>>s,m.insert({s,p--});
        for(i=0;i<n;i++){
            cin>>s;
            a+=q(m[s]);
            u(m[s]);
        }
        cout<<a<<"\n";
    }
}