본문 바로가기

Hanum.

10815 숫자 카드 본문

카테고리 없음

10815 숫자 카드

Han-um 2017. 1. 24. 00:23

10815 숫자 카드

https://www.acmicpc.net/problem/10815


 

◆ 문제 풀이


배열 두개를 입력받아, 뒤에 입력받은 배열의 숫자가 앞 배열에 포함되어있을 경우 1을, 아닐 경우 0을 출력하는 문제입니다.

 

 

시간 초과가 핵심

간단한 방법 = 선형 탐색으로는 문제의 시간 제한을 통과할 수 없으므로, 시간을 단축할 방법을 찾아야 합니다.

 

■ 선형 탐색보다 이진 탐색이 빠름

가장 대표적인 해결책은 선형 탐색이 아닌 이진 탐색을 이용하여 탐색 시간을 단축하는 것입니다.

 

■ 이진 탐색을 위한 정렬 필요

이진 탐색을 위해서는 탐색 대상 배열이 정렬되어있어야 합니다. 이를 위해 STL의 Sort 함수를 이용합니다.

 

 

 


◆ 코드

 

 

#include <iostream>
#include <stdio.h>
#include<vector>
#include<algorithm>

using namespace std;


int bar_search(vector<int> sang, vector<int> arr, int begin, int end, int key) {
 int mid;

 while (begin<=end) {
  mid = (begin + end) / 2;
  if (key == sang.at(mid)) { // SANG의 절반에 해당하는 mid와 arr의 해당 수를 같은지 비교
   return 1; // 맞으면 1반환
  }
  else if (key > sang.at(mid)) {
   begin = mid + 1;
  }
  else {
   end = mid - 1;
  }
 }
 return -1;
}

int main(){
 int num_a,num_b,temp;
 cin >> num_a;
 vector<int> sang;

 for (int i=0; i < num_a; i++) { // 상근이가 가진 카드 입력
  cin >> temp;
  sang.push_back(temp);
 }

 cin >> num_b;
 vector<int> arr;
 vector<int> arr_chk;

 for (int i = 0; i < num_b; i++) { // 배열 입력받음, 체크배열 0으로 초기화
  cin >> temp;
  arr.push_back(temp);
  arr_chk.push_back(0);
 }


 // 비교하기 이전, 이진탐색을 위해 상근이가 가진 카드 정렬
 sort(sang.begin(), sang.end());

 for (int i = 0; i < arr.size(); i++) {
  temp = bar_search(sang,arr , 0, sang.size(), arr.at(i));
  
  if (temp == -1) {
  }
  else {
   arr_chk[i] = 1;
  }
 }


 for (int i = 0; i < arr_chk.size(); i++) { // 결과값 출력
  cout << arr_chk[i] << " ";
 }

 return 0;
}

 

 



by. 구 본철

Comments