Gidhub BE Developer

# [BOJ] 숫자 카드 2

2018-02-11
goodGid

## Problem

Problem URL : 숫자 카드 2

## Answer Code (1) [18. 02. 11]

``````
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int ans;
void go(int value){
if (! binary_search(v.begin(), v.end(), value)){
ans = 0;
printf("%d ",0);
return ;
}

int l = 0, r = (int) v.size()-1;
int cnt = 0;
while (l <= r) {
int mid = ( l + r ) >> 1;

if( value == v[mid]){
// [1]
/*
for( int i=l; i<=r; i++)
if( value == v[i] )
ans ++;
break;
*/

// [2]
cnt ++;
for(int i=mid+1; v[i] == value; i++){
cnt++;
}
for(int i=mid-1; v[i] == value; i--){
cnt++;
}
break;
}
else if( value > v[mid] ){
l = mid + 1;
}
else {
r = mid - 1;
}
}
ans = cnt;
printf("%d ",ans);
}

int main() {
int n,m;
cin >> n;

int input;
for(int i=0; i<n; i++){
scanf("%d",&input);
v.push_back(input);
}
sort(v.begin(), v.end());

// Sector 1 Begin
cin >> m;
vector<int> v2;
for(int i=0; i<m; i++){
scanf("%d",&input);
v2.push_back(input);

// [3]
if( i>0 ){
if( v2[i] == v2[i-1]){
printf("%d ",ans );
continue;
}
}
go(input);
}
// Sector 1 End

// Sector 2 Begin
cin >> m;
int pre_input = 10000001 ;
for(int i=0; i<m; i++){
scanf("%d",&input);

if( input == pre_input ){
printf("%d ",ans );
pre_input = input;
continue;
}

pre_input = input;
go(input);
}
// Sector 2 End

return 0;
}

``````

## Answer Code (2) [18. 02. 11]

``````
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(void) {
int n;
scanf("%d", &n);
vector<int> v;
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
v.push_back(num);
}
sort(v.begin(), v.end());
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int num;
scanf("%d", &num);
if (binary_search(v.begin(), v.end(), num) == 0) {
printf("0 ");
}
else{
printf("%ld ", upper_bound(v.begin(), v.end(), num) - lower_bound(v.begin(), v.end(), num));
}
}
}

``````

## Answer Code (3) [18. 02. 11]

``````
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int arr[20000005];
int n, m;

int main() {
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
arr[10000000 + x]++;
}
scanf("%d", &m);
while (m--) {
int x; scanf("%d", &x);
printf("%d ", arr[x + 10000000]);
}
return 0;
}

``````

## Code Review

### Answer Code (1) [18. 02. 11]

[1] or [2] 두개다 맞다 !

[3]을 넣으니까 맞는다.

넣지 않으면 97% 시간 초과가 뜬다.

저 Code는

i 번째 일 때 i-1과 같은지만 체크해주는건데 …

저 Code 1줄이 그렇게 큰 역할을 하다니

ex) 5 5 5 5 5 5 5 이런식이면

[3]에 의해서 go()함수를 돌지 않는다.

이 부분에서 시간을 단축시키는 구나 !

Sector 1 의 논리를 파악하고 나니

굳이 v2를 사용할 필요가 없어서

Sector 2 처럼 바꿨다.

역시나 논리가 같으니 맞았습니다 !

### Answer Code (2) [18. 02. 11]

Code By 임재훈

upper_bound(v.begin(), v.end(), num)

lower_bound(v.begin(), v.end(), num))

2개의 함수에 대해 공부를 해보자 !

Answer Code (1)에서 [1]과 [2]의 로직을

`upper_bound()``lower_bound()`를 이용하여 구현한다.

2개의 함수를 정리한 Post를 참고하자 !

### Answer Code (3) [18. 02. 11]

배열로 음수를 표현 못하니까

최대 음수값을 양수로 만들어서 표현하다니 …

Code Review 할 때

아이디어에 놀랐다.

## Reivew [18. 02. 11]

• 내 로직이 왜 틀릴까 … 그래서 이것 저것 조금씩 바꿔가면서 체크해봤다.

• 시간은 많이 할애하였지만 그 만큼 많이 배웠다.

Back : DB