'Computer Science/알고리즘' 카테고리의 글 목록

Computer Science/알고리즘

2018. 11. 27. 17:29

[Javascript] 마니또 알고리즘(리스트 셔플 List shuffle)

가끔 오프라인으로 종이뽑기로 하면 본인을 뽑는 경우도 있는데 마니또는 본인 말고 다른 사람을 뽑는 알고리즘입니다.

O(n^2)이라 좋은 알고리즘은 아닌거 같은데 다른 방법을 생각해내지 못했습니다.

A, B, C, D, E 5명이 서로 다른 사람을 뽑게 하려면 A부터 순서대로 1~5번까지의 숫자를 뽑는데 1번을 제외한 숫자를 뽑도록 했습니다.

우선 랜덤한 숫자를 먼저 뽑는데 0부터 4의 숫자가 랜덤하게 추출됩니다.(while문 조건중 i == temp 를 빼면 리스트 셔플이 될 것입니다.)

while(i == temp || result.includes(temp))

이 조건은 자기 자신을 뽑지 않고 이미 뽑힌 사람은 뽑지 않는 조건이고, 자기 자신이거나 result에 숫자가 있을 경우엔 True가 되므로 False가 될 때까지 반복 추출을 합니다.

	var dbconnect = require('./sqlite');

	exports.createtable = function(){
	var name_list = ['A', 'B', 'C', 'D', 'E'];
	var result = [];
	for(var i=0; i < name_list.length; i++){
	var temp = Math.floor(Math.random()*name_list.length);
	while(i == temp \|\| result.includes(temp)){
	temp = Math.floor(Math.random()*name_list.length);
	}
	result.push(temp);

	var ins_sql = `INSERT into member (name, manitto) VALUES (?, ?)`

	var ins_list = [name_list[i], name_list[result[i]]]
	console.log(ins_list)
	dbconnect.insert(ins_sql, ins_list, function(db){});
	}

	}

이 코드에선 추출 결과를 저장하기 위해 DB에 Insert 하도록 했습니다.

다른 아이디어가 있으시면 댓글로 남겨주세요!ㅎㅎ

PREV 1 NEXT