λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
✨ Algorithm

[λ°±μ€€/C++] 2776번: μ•”κΈ°μ™•

by nitronium102 2022. 7. 17.

문제

μ—°μ’…μ΄λŠ” μ—„μ²­λ‚œ κΈ°μ–΅λ ₯을 가지고 μžˆλ‹€. κ·Έλž˜μ„œ ν•˜λ£¨ λ™μ•ˆ λ³Έ μ •μˆ˜λ“€μ„ λͺ¨λ‘ κΈ°μ–΅ ν•  수 μžˆλ‹€. ν•˜μ§€λ§Œ 이λ₯Ό 믿을 수 μ—†λŠ” λ™κ·œλŠ” 그의 κΈ°μ–΅λ ₯을 μ‹œν—˜ν•΄ 보기둜 ν•œλ‹€. λ™κ·œλŠ” 연쒅을 따라 λ‹€λ‹ˆλ©°, 연쒅이 ν•˜λ£¨ λ™μ•ˆ λ³Έ μ •μˆ˜λ“€μ„ λͺ¨λ‘ ‘수첩1’에 적어 λ†“μ•˜λ‹€. 그것을 λ°”νƒ•μœΌλ‘œ κ·Έκ°€ μ§„μ§œ 암기왕인지 μ•Œμ•„λ³΄κΈ° μœ„ν•΄, λ™κ·œλŠ” μ—°μ’…μ—κ²Œ M개의 μ§ˆλ¬Έμ„ λ˜μ‘Œλ‹€. 질문의 λ‚΄μš©μ€ “XλΌλŠ” μ •μˆ˜λ₯Ό 였늘 λ³Έ 적이 μžˆλŠ”κ°€?” 이닀. 연쒅은 λ§‰νž˜μ—†μ΄ λͺ¨λ‘ λŒ€λ‹΅μ„ ν–ˆκ³ , λ™κ·œλŠ” 연쒅이 λ΄€λ‹€κ³  μ£Όμž₯ν•˜λŠ” 수 듀을 ‘수첩2’에 적어 λ‘μ—ˆλ‹€. 집에 λŒμ•„μ˜¨ λ™κ·œλŠ” 닡이 λ§žλŠ”μ§€ ν™•μΈν•˜λ € ν•˜μ§€λ§Œ, 연쒅을 λ”°λΌλ‹€λ‹ˆλŠλΌ λ„ˆλ¬΄ νž˜λ“€μ–΄μ„œ μ—¬λŸ¬λΆ„μ—κ²Œ 도움을 μš”μ²­ν–ˆλ‹€. λ™κ·œλ₯Ό 도와주기 μœ„ν•΄ ‘수첩2’에 μ ν˜€μžˆλŠ” μˆœμ„œλŒ€λ‘œ, 각각의 μˆ˜μ— λŒ€ν•˜μ—¬, ‘수첩1’에 있으면 1을, μ—†μœΌλ©΄ 0을 좜λ ₯ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•΄λ³΄μž.

μž…λ ₯

첫째 쀄에 ν…ŒμŠ€νŠΈμΌ€μ΄μŠ€μ˜ 개수 Tκ°€ λ“€μ–΄μ˜¨λ‹€. λ‹€μŒ μ€„μ—λŠ” ‘수첩 1’에 적어 놓은 μ •μˆ˜μ˜ 개수 N(1 ≤ N ≤ 1,000,000)이 μž…λ ₯으둜 λ“€μ–΄μ˜¨λ‹€. κ·Έ λ‹€μŒ 쀄에  ‘수첩 1’에 μ ν˜€ μžˆλŠ” μ •μˆ˜λ“€μ΄ N개 λ“€μ–΄μ˜¨λ‹€. κ·Έ λ‹€μŒ μ€„μ—λŠ” ‘수첩 2’에 적어 놓은 μ •μˆ˜μ˜ 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, λ‹€μŒ 쀄에 ‘수첩 2’에 적어 놓은 μ •μˆ˜λ“€μ΄ μž…λ ₯으둜 M개 λ“€μ–΄μ˜¨λ‹€. λͺ¨λ“  μ •μˆ˜λ“€μ˜ λ²”μœ„λŠ” int 둜 ν•œλ‹€.

좜λ ₯

‘수첩2’에 μ ν˜€μžˆλŠ” M개의 숫자 μˆœμ„œλŒ€λ‘œ, ‘수첩1’에 있으면 1을, μ—†μœΌλ©΄ 0을 좜λ ₯ν•œλ‹€.

풀이

정렬을 ν•  ν•„μš”μ—†μ΄ μ‚½μž…κ³Ό κ²€μƒ‰λ§Œ μΌμ–΄λ‚œλ‹€.  μž…λ ₯의 μˆ˜κ°€ μ΅œλŒ€ 1,000,000μ΄λ―€λ‘œ O(logN)의 set이 μ•„λ‹Œ O(1)인 unordered_set을 μ‚¬μš©ν•œλ‹€.

1. μ‹œκ°„μ΄ 짧기 λ•Œλ¬Έμ— μ•žμ— μ½”λ“œ 3쀄을 λ„£μ–΄μ£Όμ–΄μ•Ό ν•œλ‹€.

2. set의 경우 μ•„λž˜ 방식 쀑 ν•˜λ‚˜λ₯Ό μ„ νƒν•˜λ©΄ 될 λ“―ν•˜λ‹€. 제일 μœ„μ— μ„ μ–Έν•˜κ³  μ΄ˆκΈ°ν™”λ₯Ό ν•˜μ§€ μ•Šμ•˜λ”λ‹ˆ 자꾸 μ‹€νŒ¨κ°€ λ–΄λ‹€^^
(1) whileλ¬Έ μ•ˆμ—μ„œ μ„ μ–Έν•˜μ—¬ μžλ™ μ΄ˆκΈ°ν™”

(2) 제일 μœ„μ— μ„ μ–Έν•˜κ³  λλ§ˆλ‹€ μ΄ˆκΈ°ν™”

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    // μ‹œκ°„ 초과 방지
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t, n, m, num;

    // μž…λ ₯
    cin >> t;
    while (t--) {
        unordered_set<int> note;
        cin >> n;
        while (n--) {
            cin >> num;
            note.insert(num);
        }

        cin >> m;
        while (m--) {
            cin >> num;
            if (note.find(num) == note.end())
                cout << "0\n";
            else
                cout << "1\n";
        }
    }
}

λŒ“κΈ€