글 읽기 - 1920번 시간초과

dmlwlsdk07 7년 전 0

못하긴 했지만... 뭐가 문제죠?

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

using namespace std;

int main()
{
	int i, j, k, m, n ,lo, hi, mid, ck=0;
	int a[100000];
	int b[100000];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	scanf("%d",&m);
	for(i=0;i<m;i++){
		scanf("%d",&b[i]);
	}
	sort(a,a+n);
	for(i=0;i<m;i++){
		lo=0; hi=n;
		mid=(lo+hi)/2;
		while(lo<hi){
			if(b[i]<a[mid]){
				hi=mid;
			}
			else if(b[i]>a[mid]){
				lo=mid;
			}
			else if(b[i]==a[mid]){
				b[i]=1;
				k=1;
				break;
			}
			mid=(lo+hi)/2;
			if(mid>=n-1)
				break;
			for(j=lo;j<=hi;j++){
				if(a[j]==b[i]){
					b[i]=1;
					k=1;
					break;
				}
			}
			if(k==1){
				break;
			}
		}
		if(k==0)
			b[i]=0;
		k=0;
	}
	for(i=0;i<m;i++){
		printf("%d\n",b[i]);
	}
}

ghkdtkden93 7년 전 1

시간복잡도에 의하면 초과되요... 이거 자료구조 선택이 중요해요

탐색이 빠른 자료구조 map,set을 추천합니다.

연관컨테이너 이용하시면 될거예요. 저도 첨에 틀렸네요...

그리고 iostream말고 scanf사용하시구요

http://dream-cy.tistory.com/10 참조
- 시퀀스 컨테이너 : 순서 있게 자료를 보관하는 컨테이너 (vector, list, deque)
- 연관 컨테이너 : key, value 형태로 짝을 이뤄 자료를 보관하는 컨테이너 (map, set)

dmlwlsdk07 7년 전 0

감사합니다!!!!

kmg8280 7년 전 1

맵을쓰세용.

#pragma warning (disable:4996)
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<memory.h>
#include<string>
#include<map>
using namespace std;
int arr[2000000];
int main()
{
    int n, m;
    map<string, int> M;
    string x;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        M[x]++;
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> x;
        if (M[x] >= 1)
        {
            cout << 1 << endl;
        }
        if (M[x] == 0)
        {
            cout << 0 << endl;
        }
    }
    return 0;
}

dmlwlsdk07 7년 전 0

근데 이분탐색을 써야하는거 아니었나요?

ghkdtkden93 7년 전 0

그게 더 좋을 거 같긴하네요..

어쨌든 탐색에 유리한 형태를 써야되는거죠..

전 이거보고 set_hash 가 떠올라서.. 정답은 여러개죠.. 프로그래밍에서 ㅋㅋ

gowithmylord 7년 전 0

이분탐색으로 해내신분 있으면 보고싶다..

lexio 7년 전 1

@gowithmylord stl sort, binary_search만 해도 될꺼에요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1920번 시간초과

dmlwlsdk07 7년 전 0

ghkdtkden93 7년 전 1

dmlwlsdk07 7년 전 0

kmg8280 7년 전 1

dmlwlsdk07 7년 전 0

ghkdtkden93 7년 전 0

gowithmylord 7년 전 0

lexio 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말