Gidhub BE Developer

BOJ - 숫자 카드 2

2018-02-11
goodGid

Problem

Problem URL : 숫자 카드 2

Screenshots of Problem Explain

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]

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

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


Comments

Content