Facebook Joinc 그룹
Joinc QA 사이트
Tweet
joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.
현재위치 : thinking about search
Tweet
joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.
어느 외국인 서버 개발자하고 얘기중에 이 문제와 알고리즘 얘기를 하더군요. 나름대로 괜찮은 알고리즘같습니다.
혹, 더 좋은 방법이나 이 방법의 문제점이 있다면 글을 달아주세요.
혹, 더 좋은 방법이나 이 방법의 문제점이 있다면 글을 달아주세요.
S = { 3, 10, 2, 99, 243, ... } 등의 Integer형 n개의 원소를 가진 집합 S가 있습니다.
그리고 Integer형 K 가 있습니다.
S의 어떤 두 원소를 합해서 K 와 일치하는게 있다면 True를 하나도 없다면 False를 반환하는 함수를 만들어보세요.
한 원소를 두 번 더하는 경우도 체크합니다.
단, 가장 효율적인 함수를 생각해보시기 바랍니다. 평균복잡도가 O(n)이 될 수 있는...
#define NUM 1000000
#define KEY 350
#include <iostream>
#include <map>
#include <stdlib.h>
using namespace std;
class Data {
private:
int data[NUM];
map<int, bool> mapData;
public:
Data (void);
bool judge (int key);
};
Data :: Data(void) {
int i;
for (i = 0; i < NUM; i++) data[i] = random() % NUM;
}
bool Data :: judge(int key) {
int i;
for (i = 0; i < NUM; i++) mapData[key - data[i]] = true;
for (i = 0; i < NUM; i++) if (mapData[data[i]]) return(true);
return(false);
}
int main(void) {
Data data;
if (data.judge(KEY)) cout << "Same pair exist" << endl;
else cout << "Same pair not exist" << endl;
return(EXIT_SUCCESS);
}