[백준,C++] 10816 : 숫자 카드 2

728x90

문제

---

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

SMALL

입력

---

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

반응형

출력

---

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

처음에는

딱 봐도 일반적인 선형 탐색을 하면 너무 오래 걸릴 것 같아서

오름 차순으로 정렬후

 

중간 값을 찾아봐 찾으려는 값이 중간 값보다 크면 뒤에서 부터

작으면 앞에서 부터 찾아보는 코드를 찾으려 했는데

 

시간 초과가 떠서 그를 더 최적화해

오름 차순으로 정렬 후 예를 들어 1,2,3,3,3,3,3,3,4,5,6,6,7,8,8,9 이런 배열이 되었을 때

6을 찾을 떄 뒤에서 시작해 이 배열의 끝까지 탐색 하는게 아니라

6이 끝나는, 즉 5에서 부터는 탐색을 그만하도록 코드를 짰는데

이런

이것도 시간 초과가 났다

 

그래서 발견한 풀이는 두가지이다

 

<Hash Map인 map 라이브러리 사용>

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;



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

  int N,M,x;
  cin >> N;
  map<int, int> arr;
  for (int i = 0; i < N; i++) {
    cin >> x;
    arr[x]++;
  }

  cin >> M;
  for (int i=0; i<M; i++){
    cin >> x;
    cout << arr[x] << " ";
  }
}

 

일단 map을 사용하기 위해 상단에 #include <map>을 추가해주고

map<int, int>를 통해 index도 int, value도 int로 해준다

 

그 후로 x에 있는 값을 ++ 해줌으로서

나중에 출력 할 때 그 index가 몇번 입력 됐는지 출력하면 되는

공간 복잡도가 매울 효율적인 코드이다

 

+이 코드 라인들은 입력 및 출력 작업을 최적화하기 위한 것이다. `ios_base::sync_with_stdio(0);`은 C++ 표준 스트림 (cin, cout 등)을 C 표준 I/O 함수들과 동기화하는 데 사용되며, 이는 입력 및 출력 작업의 성능을 향상시킬 수 있다. `cin.tie(0);`는 cin을 cout에서 untie하는 데 사용되며, 이 역시 성능 이점을 제공할 수 있다.

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."

 

<이분탐색, upper_bound-lower_bound>

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

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

  int N,M,x;
  cin >> N;
  int arr[N];
  for(int i=0; i<N; i++){
    cin >> arr[i];
  }

  sort(arr, arr+N);

  cin >> M;
  for(int i=0; i<M; i++){
    cin >> x;
    cout << upper_bound(arr, arr+N, x) - lower_bound(arr, arr+N, x) << " ";
  }
    
}

 

- upper_bound : 찾고자 하는 값의 다음 값이 최초로 나타나는 위치

- lower_bound : 찾고자 하는 값 이상이 처음 나타나는 위치

즉 사용하려면 sorting되어 있어야한다

 

그럼으로 upperbound-lowerbound를 하면 그 수의 출현 횟수를 찾을 수 있다

 

<[백준,C++] 1920 : 수 찾기>
https://tonnykang.tistory.com/91

[백준,C++] 1920 : 수 찾기