[백준 1920] 수 찾기 (C#, C++) - soo:bak

문제 링크

1920번 - 수 찾기

설명

입력으로 주어지는 n 개의 숫자들 중에, 이어서 입력으로 주어지는 m 개의 숫자 각각이 존재하는지 판별하는 문제입니다.

문제의 범위와 시간 제한을 고려하였을 때, 완전 탐색을 활용하여서는 풀이할 수 없습니다.

따라서, 이분 탐색 알고리즘과 같은 보다 효율적인 탐색 알고리즘을 사용하거나, 탐색을 위해 효율적인 자료구조를 사용해야 합니다.

C++ 의 unordered_set 자료구조는 특정 요소에 대한 존재 여부를 빠르게 탐색할 수 있는 자료구조입니다.

unordered_set 자료구조는 해시 테이블을 기반으로 고유한 해시 값에 대해 직접 접근할 수 있기 때문에,

특정 원소의 존재 여부를 상수 시간으로 확인할 수 있습니다.

C# 에서는 HashSet 자료구조를 사용하였으며, StringBuilder 을 사용하지 않으면 시간 초과 가 됨에 주의합니다.

---

Code

[ C# ]

namespace Solution {
  using System.Text;
  class Program {
    static void Main(string[] args) {

      var n = int.Parse(Console.ReadLine()!);

      var nums = new HashSet<int>();
      var input = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();
      foreach (var num in input)
        nums.Add(num);

      var m = int.Parse(Console.ReadLine()!);
      var queries = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();

      var sb = new StringBuilder();

      for (int i = 0; i < m; i++) {
        if (nums.Contains(queries[i])) sb.AppendLine("1");
        else sb.AppendLine("0");
      }

      Console.Write(sb.ToString());

    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;

  unordered_set<int> nums;
  for (int i = 0; i < n; i++) {
    int num; cin >> num;
    nums.insert(num);
  }

  int m; cin >> m;

  for (int i = 0; i < m; i++) {
    int query; cin >> query;
    if (nums.count(query)) cout << 1 << "\n";
    else cout << 0 << "\n";
  }

  return 0;
}