백준 1920번 [수 찾기](C++)-yes6686- 티스토리

백준 문제 풀이: 1920 [수 찾기]

---

문제 링크: https://www.acmicpc.net/problem/1920

문제 설명:

정수 N개로 이루어진 배열 A에서 특정 정수들이 존재하는지 확인하는 문제입니다. 각각의 정수에 대해 존재 여부를 1 또는 0으로 출력합니다.

---

문제 해결 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    map<string, int> m;
    int n;
    cin >> n;
    string x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        m.insert(pair<string, int>(x, 1));
    }

    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> x;
        auto iter = m.find(x);
        if (iter != m.end()) {
            cout << 1 << '\n';
        } else {
            cout << 0 << '\n';
        }
    }
}

---

코드 설명

• 입력: 배열 A의 크기(N)와 정수들, 그리고 확인할 정수들(K)이 주어집니다.
• 맵(map) 자료구조 사용:
  • 배열 A의 각 원소를 키(key)로 저장하여 존재 여부를 빠르게 확인합니다.
  • 맵의 삽입 연산은 O(log N)이므로 효율적입니다.
• 검색: 맵에서 키를 검색하여 해당 정수가 존재하면 1, 없으면 0을 출력합니다.
• 시간 복잡도: O((N + K) log N)
  • 삽입: N개의 원소를 맵에 삽입 → O(N log N)
  • 검색: K개의 정수를 맵에서 검색 → O(K log N)

---

결과

입력된 정수들의 존재 여부를 빠르게 확인할 수 있습니다. 맵을 사용하여 검색 효율성을 최적화한 풀이입니다.

다른 풀이 방법이나 개선 사항이 있다면 댓글로 남겨주세요!