AtCoder ABC392 C問題 Bib with C++ & Swift code

#Info

https://atcoder.jp/contests/abc392/tasks/abc392_c

C - Bib

 

Github Link C++ 

https://github.com/novvvv/PS/blob/main/atCoder/C%2B%2B/ABC392_C%E5%95%8F%E9%A1%8C_Bib.cpp

PS/atCoder/C++/ABC392_C問題_Bib.cpp at main · novvvv/PS

 

Github Link Swift

https://github.com/novvvv/PS/blob/main/atCoder/swift/AtCoder%20Beginner%20Contest%20392%20B%20-%20Who%20is%20Missing%3F.swift

PS/atCoder/swift/AtCoder Beginner Contest 392 B - Who is Missing?.swift at main · novvvv/PS

 

---

#Solve

구현보다 문제의 요구사항이 뭔지 너무 말을 꼬아놔서 지문을 이해하는데 더 시간을 사용했던 문제였다. 

요구사항은 다음과 같다.

 

총 1~n의 서로 다른 번호가 적힌 티셔츠를 입고 있는  n명의 사람이 주어진다. 

q[i] - i번째 사람이 입고 있는 번호표이다. q[3] = 4 라면, 3번째 사람은 숫자 4가 적힌 셔츠를 입고 있다는 뜻이다.

p[i] - i번째 사람이 보고 있는 사람이다. p[1] = 3이라면, 1번째 사람은 3번째 사람을 보고 있다는 뜻이다. 

 

우리가 구해야 할 값은 번호 i를 입고 있는 사람이 보고 있는 사람의 번호표이다. 

BruteForce 알고리즘을 사용해서 탐색하면 O(N^2)으로 시간초과가 발생하기에 O(N)에 문제를 해결하기 위해 HashMap + Indexing 하는 방식을 채택하였다. 

 

이제 요구사항과 사용해야 할 자료구조를 모두 파악했으니 차근차근 문제의 조건대로 코드를 구현해 나가면 된다. 

    int n; // 2 ~ 300000
    cin >> n;
    int p[300001] = {0, };
    int q[300001] = {0, };
    map<int, int> people;
    for (int i = 1; i <= n; i++) cin >> p[i]; // i번째 사람이 발견한 사람
    for (int i = 1; i <= n; i++) cin >> q[i]; // I번째 사람이 입고있는 번호표

 

people[q[i]] = i번째 티셔츠를 입고 있는 사람의 정보

    for (int i = 1; i <= n; i++) {
        people[q[i]] = i;
    }

 

p[people[q[i]] = i번째 티셔츠를 입고 있는 사람이 보고 있는 사람

q[p[people[i]]] = i번째 티셔츠를 입고 있는 사람이 보고있는 사람이 입고있는 셔츠 

    for (int i = 1; i <= n; i++) {
        cout << q[p[people[i]]] << " ";
    }

 

처음에 말만 들으면 정신이 혼미해질 수 있으나.......차근차근 문제에서 원하는 조건을 구현해 나가면 된다.