[코드포스 Practice14] B. Find The Bone

 

풀이는 간단하다.

k개 swap을 하면서 뼈다귀를 섞는데 바꿀 위치가 구멍인지 아닌지 파악하면 된다.

 

여기서 구멍인지 아닌지 파악하는 부분을 단순히 찾으면 시간복잡도가 O(N)이 걸려서 전체적으로 O(N^2)이 된다. 

그래서 이걸 이분탐색으로 바꿔 O(NlogN)이 되게 했다. 찾는 함수는 lower_bound를 썼음

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<int> v(n + 1, 0);
    v[1] = 1;
    
    vector<int> h(m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &h[i]);
        if (h[i] == 1)
        {
            printf("1");
            return 0;
        }
    }
    
    sort(h.begin(), h.end());
    for (int i = 0; i < k; i++)
    {
        int u1, u2;
        scanf("%d %d", &u1, &u2);
        
        std::vector<int>::iterator pos = lower_bound(h.begin(), h.end(), u1);
        if (*pos == u1 && pos != h.end())
        {
            printf("%d", *pos);
            return 0;
        }
        pos = lower_bound(h.begin(), h.end(), u2);
        if (*pos == u2 && pos != h.end())
        {
            printf("%d", *pos);
            return 0;
        }
        
        int tmp = v[u1];
        v[u1] = v[u2];
        v[u2] = tmp;
    }
    for (int j = 1; j <= n; j++)
    {
        if (v[j] == 1)
        {
            printf("%d", j);
            break ;
        }
    }
    return 0;
}

 

코드는 이렇게 짰다.

이 문제 계속 원인 못 찾고 6번에서 틀렸었는데 알고보니 구멍 확인하는 부분에서 문제가 있었다.

 

        std::vector<int>::iterator pos = lower_bound(h.begin(), h.end(), u1);
        if (*pos == u1 && pos != h.end())
        {
            printf("%d", *pos);
            return 0;
        }
        pos = lower_bound(h.begin(), h.end(), u2);
        if (*pos == u2 && pos != h.end())
        {
            printf("%d", *pos);
            return 0;
        }

 

ㅋㅋㅋㅋ

아니 그냥 구멍 있으면 바로 위치 찾았다고 해버렸네

 

옮기는 게 뼈다귀가 있고 구멍이 있다면 맞았다고 해야했다.

 

        std::vector<int>::iterator pos = lower_bound(h.begin(), h.end(), u1);
        if (*pos == u1 && pos != h.end() && v[u2] == 1)
        {
            printf("%d", *pos);
            return 0;
        }
        pos = lower_bound(h.begin(), h.end(), u2);
        if (*pos == u2 && pos != h.end() && v[u1] == 1)
        {
            printf("%d", *pos);
            return 0;
        }

 

그래서 이렇게 바꿨다.

 

결과는 모르겠다. 아직도 코포 안 들어가짐 

 

와!

맞았다! ^___^